New answers tagged elementary-number-theory
0
votes
Quadratic irrationals with continued fraction of period one
Let $p/q$ be a rational fraction and $p'/q'$ be its penultimate CF approximant, both rendered in lowest terms. If $m=\frac12(n+\sqrt{n^2+4})$ is a metallic mean, then the CF for the ratio
$\dfrac{mp+p'...
0
votes
There exist two square-free numbers, each with a given amount of factors, that differ by a given amount.
This is an incomplete answer, relating your question to Dickson's conjecture which is presently unproven. It does suggest that your claim holds when $m,n>1$, and I'm sure that with some effort or a ...
0
votes
Accepted
Can two irrational numbers satisfy these conditions?
Take $$P= \frac12 \left(1 + 3 \sqrt2 + \sqrt{15 + 6 \sqrt2}\right)$$
And
$$Q=\frac12 \left(-1 + 3 \sqrt2 - \sqrt{15 - 6 \sqrt2}\right)$$
The values of your expressions are, in order,
$$17$$
$$\frac{19+...
1
vote
Accepted
How to prove $ax+by\equiv c\pmod{n}$ has a solution if and only if $gcd(a,b,n)\mid c$?
According to Bézout's identity, there exist three integers $x_1, x_2, x_3$ such that
$
a x_1 + b x_2 + n x_3 = d
$
We know that $c = d e$ for some integer $e$. Hence
$ a e x_1 + b e x_2 + n e x_3 = c $...
0
votes
Accepted
Symmetry (group) arising from modular arithmetic
The question, in essence, asks that, given $k\not \equiv \pm 1\pmod n$, and given $a\pmod n$ can we always find $i, j\pmod n$ such that $$i+kj\equiv 0 \quad \quad \&\quad \quad j+ki\equiv a \tag1$$...
3
votes
Number Theory Problem related to GCD and sequence from an Olympiad
Another way. These two preliminary results are easy to prove
► By telescopy we have $a_n+n=a_0+(a_0^2+a_1^2+....+a_{n-1}^2)$ for all $n\ge1$.
►► If $p|a_n$ then $a_{n+k}\equiv-1\pmod p$ for all $k$.
...
2
votes
Accepted
Satisfying $Sd(S)$ modular conditions with $O(S)$ points
Let $S=p^n$ for a prime $p$. For $k=0,\cdots, p^n-1$, let $x_k=k$. Write $k$ as an $n$ digit number base $p$ and reverse the digits (including leading $0$'s up to $n$'th digit) and let $y_k$ be the ...
0
votes
How far away is a number from being a power?
You can trivially calculate the 2nd, 3rd, 4th etc root of n, rounded to the nearest integer. And you don't need k-th roots where k is composite, saving quite a lot of work. For small n, say n ≤ 10^10, ...
6
votes
Accepted
How far away is a number from being a power?
The distance from $n$ to the nearest $k$th power of an integer is exactly $\min\{ n-\lfloor m^{1/k}\rfloor^k,\lceil m^{1/k}\rceil^k - n \}$. Therefore if $n\le2^B$, the distance from $n$ to the ...
1
vote
Accepted
What types of operations on linear congruences yield extraneous solutions?
While performing $7x-(39x-5\cdot7x)$, "equation $(17)$" was multiplied by $1-(-5)$, which is not coprime to $39$.
Other point of view: "equation $(17)$" is equivalent to equation $(...
2
votes
Accepted
Show 7 is a generator of $\left(\mathbb{Z} \backslash p \mathbb{Z} \right)^*$ given that it is a quadratic noresidue.
Since $7$ is a quadratic non-residue modulo $p$, it follows that $7^{\frac{p-1}{2}} \equiv -1 \pmod p$. Since $p = 2^{2^n} + 1$, this implies $7^{2^{2^n -1}} \equiv -1 \pmod{p}$, which implies that $7^...
3
votes
Does using pre-computed squares speed up significantly the calculation of factorial $n!$?
Let say I need to calculate $1000!$.
$1000!$ has $2568$ digits in base$10$, so we have to pre-compute all the squares up to $10^{2568}$ (approx). It is not possible to store the table with this size ...
2
votes
Doubt regarding the prime counting function $\pi(n)$
You may use the bounds $\frac{x}{\log x}\lt \pi(x)\lt \frac{3x}{2\log x}$ for $x\geq 17$. It follows $\pi(n^2)-\pi\left(\left\lfloor \frac{n^2}{2}\right\rfloor\right) \gt \frac{n^2}{2\log n} - \frac{...
5
votes
How *exactly* is divisibility defined?
In addition to freakish’s answer, one might note that in a noncommutative ring (such as the Hurwitz integers $H$, the ring of quaternions with either all integer or all half-integer components), there ...
0
votes
$x$ is rational if $x^5$ and $20x+\frac {19}x$ are rational
Say $x^5 = t,$ $a=20$ & $b=19.$
We proceed as follows:
\begin{equation}
a^2x^2 + \frac{b^2}{x^2} = \left(ax + \frac{b}{x}\right)^2 - 2ab \in \mathbf{Q} \tag{1}
\end{equation}
\begin{equation}
a^...
0
votes
If $(a, b) = 1$ and $n$ is a prime then prove that $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factors unless $a+b$ is a multiple of $n$.
Here's a relatively standard solution using LTE. Suppose $p$ is a prime that divides $a+b$. In particular; if $n\nmid a+b$ then $p\neq n$. Notice that since $a,b$ are coprime, and $p\mid a+b$, then $p\...
0
votes
If $(a, b) = 1$ and $n$ is a prime then prove that $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factors unless $a+b$ is a multiple of $n$.
For any positive integer $n$,
$$ a^n + b^n = a^n + (( a+b) + (-a))^n = a^n(1 + (-1)^n) + (a + b)^n + \sum_{j = 1}^{n-1} {n \choose j} (a + b)^j (-a)^{n-j}$$
CASE I: $n$ is an odd prime.
The $a^n$ term ...
3
votes
Accepted
at least $n^2$ different integers of the form $x+yz$ where $x,y,z \in S$
Hint
You can prove this by induction on $n$. Let $m$ be the largest number in $S$, and let $S'=S-\{m\}$. By the inductive hypothesis, you know that there are at least $(n-1)^2$ numbers of the form $xy+...
8
votes
How *exactly* is divisibility defined?
Generally in a commutative ring (or monoid) $R,$ by definition $\,a\mid b\,$ if $\,ax=b\,$ has a solution in $R$, unique $ $ iff $\,a\,$ is not a zero divisor, $ $ so then $\:a\mid b\iff b/a\in R\:$ ...
60
votes
How *exactly* is divisibility defined?
The most general definition is:
We will say that $a$ divides $b$ if there is $c$ such that $b=ac$.
Here $a,b,c$ are assumed to belong to the same "structure". I deliberately omitted the &...
4
votes
Accepted
Finding Pythagorean triples divisible into smaller Pythagorean Triples.
Here's a way to generate more examples, several of which are "small" by some metric.
Given any triple $(a, b, c)$, scaling it by $c$ produces the triple $(ca, cb, c^2)$, so the hypotenuse ...
1
vote
Multiplication Well Defined Under Integers
Observation: Verify the following :
We can multiply throughout by a scalar, namely $(kA, kB) \sim (k\bar{A} , k\bar{B})$.
We can swap coordinates, namely $(B, A) \sim (\bar{B}, \bar{A})$.
We can add ...
1
vote
How to determine the PDF of $\{a+bx\}$, the fractional part of a linear function?
$\DeclareMathOperator{\fp}{\mathrm{frac}}\DeclareMathOperator{\P}{\mathbb{P}}$Let $X$ be a random variable uniformly distributed over the set $\{1,2,\ldots,N\}$, that is
$$\P(X=k)=\frac1N,$$
for all $...
3
votes
Accepted
Can this pattern connect trigonometry and repeating decimals?
Let
$$
a(x)=\frac{10^{9d}-1}{x}
$$
where $x$ is a positive integer such that $1/x$ has a non terminating decimal fraction and $d$ is the period of repetition of that decimal fraction.
Let the last ...
1
vote
Diophantine equation: finding when a degree $2$ expression in $x$ and $y$ is a perfect square.
If you set $2x-y-1=u$ and $y-x=v$, you get a bijection between $\mathbb{Z}^2$ and $\mathbb{Z}^2$, which means that each integer solution for $(x,y)$ is also an integer solution for $(u,v)$ and the ...
0
votes
Diophantine equation: finding when a degree $2$ expression in $x$ and $y$ is a perfect square.
$$k^2=4x^2-4x(y-1)+y^2-6y+1\iff4x^2-4x(y-1)+y^2-6y+1-k^2=0$$
$$\implies x=\cdots=\dfrac{y-1\pm\sqrt{k^2+4y}}2$$
Now, as $x$ is an integer, $\sqrt{d^2+4y}$ must be an integer $=+e$(say)
$\implies y=\...
0
votes
If none of numbers: $a,a+d,a+2d,...,a+(n-1)d$ are divisible by $n$,then prove that $n,d$ are coprime.
If $\gcd(n, d) = 1$,
then we will have,$(i-j)d \equiv 0 \pmod{n}$, implying that $i-j \equiv 0 \pmod{n}$, but this is impossible since both $i$ and $j$ are less than $n$, so $\gcd(n, d) \neq 1$
1
vote
Can this pattern connect trigonometry and repeating decimals?
Not an answer, but an attempt to re-state the question.
Some observations:
For rational $s$ (strictly) between $0$ and $1$, with a repetend of length $d$ that starts immediately after the decimal ...
1
vote
How can we know if a multinomial coefficient is even or odd
You can actually work out the complete prime factorization of each factorial in the numerator and denominator pf the multinomial coefficient using Legendre's method
In your application you only need ...
-1
votes
Accepted
Why do these relations hold for repeating decimals?
Hint e.g. for $\,n=7\,$ the modulus $\,m = 142857 = (\color{#0a0}{10^6-1})/7,\,$ so $\bmod m\,$ we have $\,\color{#0a0}{10^6\equiv 1},\,$ so $\,\color{#c00}{10^{6j}}\equiv (\color{#0a0}{10^6})^j\equiv ...
1
vote
Showing there is always rational points on the curve $\sqrt{x^2-1}$, with any given range
Here is a proof based on Gerry Myerson's comments:
Let's begin with the easy part: if $x=\frac{q^2+1}{q^2-1}$, where $q$ is a rational number greater than $1$, then both $x$ and $\sqrt{x^2-1}=\frac{2q}...
1
vote
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
Just to add some details to the nice answers already posted, the subgroup of $(\mathbb{Z}/1000)^{\times}$ generated by $3$ and $7$ has order 200, so it is of index $2$ ( since $|(\mathbb{Z}/1000)^{\...
1
vote
Non-Trivial Solutions to Diophantine Equation $x^3 + x = y^3$
Note that for $x>0$ you have
$$x^3<x^3+x<(x+1)^3,$$
and for $x<0$ you have
$$(x-1)^3<x^3+x<x^3.$$
This means $x^3+x$ is not a perfect cube if $x\neq0$, so the unique integral ...
10
votes
Find all $a$ such that $n^{a}-n$ is divisible by $a \cdot (a-1)$ for any integer $n$.
For $a=1$ the problem reduces to $0\mid0$, which is true, so this is another (trivial) solution. Now let $a>1$. By Korselt's criterion, as linked in the comments, $a-1$ has to be squarefree, and ...
2
votes
Composite $2^{398}+1$ in its prime factors.
As explained in the comments,
$$
2^{398}+1=(1-2^{100}+2^{199})(1+2^{100}+2^{199}).
$$
This is enough for pari-gp to factorize it:
\begin{align*}
1-2^{100}+2^{199}& =797 \\
& \cdot ...
2
votes
Accepted
Enumeration of Permutations of $0–9$ Satisfying Closure Under Doubling
You’ve seen that we have these constraints on valid numbers (SMART numbers whose double is SMART):
(a) each digit is used exactly once;
(b) the first digit is less than $5$;
(c) for $0 ≤ i < 5$, ...
0
votes
Is it known that all primes can be expressed as a square number minus a prime number?
Comment: I found this in a book which can help to formulate the matter.
Problem: Prove that any number $n>6$ can be expressed as the sum of two numbers prime to each other.
Solution:
case 1: the ...
0
votes
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
If we look at the group generated by 3 modulo 100.
3,9,27,81,43,29, etc.
There are 20 members to this group. Every element has an even number in the 10s digit. 7 is a member of the group.
All numbers ...
-1
votes
Divisibility by $33^{33}$
My approach to this problem was quite simple. I found for which values of $k$ is $19^k+92^k$ divisible by $3$,$11$ or $33$.
I found out that:
$3 \mid 19^k+92^k$ when $k$ is odd, and $3^2|19^k+92^k$ ...
4
votes
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
Proof$_{\:\!1}$ $\!\bmod 20\!:\, 7\equiv 3^{-1}$ so $\,3^a7^b\!\equiv 3^{a-b}\!\in S\equiv \{1,3,9,7\}\,$ but $\,133\!\equiv\! 13\not\in S$ $\,\ \bf\small QED$
Proof$_{\:\!2}$ $ \bmod 4\!:\, \ \ \ \...
4
votes
Given an $n$ such that for all $m \neq n$, then $\phi(n) \neq \phi(m)$, prove that $4 \mid n$
Answering for completion :
If $n$ is not a multiple of $4$, then $n$ is either odd or an odd multiple of $2$.
If $n=2k$ with $k$ odd then $\phi(n) = \phi(2k) = \phi(2)\phi(k) = \phi(k)$.
If $n$ is odd ...
17
votes
Is it known that all primes can be expressed as a square number minus a prime number?
This seems to be unknown, and like many problems of this form, hard to approach. Indeed, in this case even if it was not true for some particular prime $p^*$, how would you even prove that $n^2-p^*$ ...
13
votes
Accepted
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
The remaining other possibility is that the number, call it $n$, has the form $3^a7^b$.
If we know the three last digits of a natural number, we also know its residue class modulo $8$. As $133\equiv5\...
6
votes
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
Not much case analysis is actually necessary here.
Say $n$ ends in $133$. It certainly isn't divisible by $2$ or $5$; so we need to show it can't be of the form $3^a 7^b$.
You can do this by looking ...
4
votes
Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.
A number with no prime factors greater than $7$ must have only prime factors in $\{2,3,5,7\}$. Such a number takes the form $2^a3^b5^c7^d$. If $n\equiv 133\bmod 1000$ takes this form, it must have no $...
0
votes
Accepted
Digit Factorial Chains - Why does every number fall into a loop?
Some notation : for $N \in \mathbb N$ let $f(N)$ be the sum of the factorials of the digits of $N$.
Let $N$ be an $n$ digit number with $n$ fixed. Then, $f(N)$ is the largest when each of its digits ...
1
vote
Criteria for a number being a square-pyramidal number
We can identify a square pyramidal number by comparing it with with an appropriately constructed cube.
Multiply the number to be tested by $24$, e.g.
$91×24=2184.$
Identify the cube root of this ...
7
votes
Accepted
Criteria for a number being a square-pyramidal number
Let's work this out in general. Suppose we wish to test whether $K = P(n)$, where $P(x)$ is a polynomial in $\mathbb{Q}[x]$. Assume there exists a polynomial $Q(x) \in \mathbb{Q}[x]$ and an integer $m ...
0
votes
$a^2 = 3^b + 37$
Comment: Starting from the solutions you found we may try to pridict the existence of more solutions. We may manipulate like this:
$3^b+3^3=a^2-10\Rightarrow a^2-10\geq 27$
In the case $a^2=27$ we ...
-1
votes
Top 50 recent answers are included
Related Tags
elementary-number-theory × 38283number-theory × 7800
modular-arithmetic × 4824
prime-numbers × 4016
divisibility × 3261
diophantine-equations × 1962
combinatorics × 1438
solution-verification × 1437
contest-math × 1429
gcd-and-lcm × 1410
algebra-precalculus × 1317
discrete-mathematics × 1118
abstract-algebra × 977
sequences-and-series × 867
polynomials × 679
induction × 671
proof-writing × 663
totient-function × 663
prime-factorization × 619
quadratic-residues × 572
integers × 500
square-numbers × 493
summation × 488
inequality × 464
factorial × 447