A natural number $n$ is said to have the property $P,$ if, for all $a, n^2$ divides $a^n - 1$ whenever $n$ divides $a^n - 1.$ a.) Show that every prime number $n$ has property $P.$ b.) Show that there are infinitely many composite numbers $n$ that possess property $P.$
Problem
Source: IMO Shortlist 1993, India 5
Tags: modular arithmetic, number theory, Divisibility, prime numbers, composite numbers, IMO Shortlist
ZetaX
15.03.2006 23:14
Non-$\LaTeX$ed problems/solutions: http://www.mathlinks.ro/Forum/viewtopic.php?t=266
Solution by grobber:
Numbers of the form $n=pq$ with $p,q$ distinct primes should work: if $p|a^{pq}-1$, then $p|a^q-1$ because $a^q\equiv (a^q)^p\pmod p$, which means that $a^{tq}\equiv 1\pmod p,\ \forall t\ge 0$, from which we get $p|a^{q(p-1)}+\ldots+a^q+1=\frac{a^{pq}-1}{a^q-1}$. This is just another way of saying that $p^2|a^{pq}-1$, and we prove that $q^2|a^{pq}-1$ in the exact same way.
Binomial-theorem
06.10.2013 09:08
(a)If $n=p$ then we arrive at \[a^p-1\equiv a-1\equiv 0\pmod{p}\]
Next, notice that when $p\neq 2$ we arrive at \[v_p(a^p-1)=v_p(a-1)+v_p(p)\ge 2\]
When $p=2$ we arrive at \[a\equiv 1\pmod{2}\implies a^2-1\equiv 0\pmod{4}\]
(b)I claim that all $n=pq$ for $p,q\neq 2 \text{ and } p\neq q$ satisfy this condition. First off notice that from the given condition we have:
\begin{eqnarray*} a^{pq}-1\equiv a^q-1\equiv 0\pmod{p} \\ \text{ord}_{p}(a)\mid q \end{eqnarray*}
Therefore $\text{ord}_{p}(a)\in \{1, q\}$.
$\begin{cases} \text{ord}_{p}(a)=1 & \implies v_p(a^{pq}-1)=v_p(a-1)+v_p(pq)\ge 2 \\ \text{ord}_{p}(a)=q &\implies v_p[(a^q)^p-1]=v_p(a^q-1)+v_p(p)\ge 2\end{cases}$
We use a similar argument to prove $q^2\mid a^{pq}-1$ and we are done $\Box$.
djmathman
02.07.2019 20:29
Observe that $2$ has the property $P$, since whenever a square is odd, it is also congruent to $1$ modulo $4$. Henceforth assume that $n$ is odd. Let $n$ be any odd positive integer such that $\gcd(n,\varphi(n)) = 1$. (EDIT 1/29/2023: This implies $\color{red}n$ is squarefree.) The condition that $n$ divides $a^n - 1$ implies that $\gcd(a,n) = 1$, so $a^{\varphi(n)} \equiv 1\pmod n$. This yields $a\equiv a^{\gcd(n,\varphi(n))} \equiv 1\pmod n$. Now for any (odd) prime $p$ dividing $n$, we see that \[ \nu_p(a^n - 1) = \nu_p(a-1) + \nu_p(n) \geq 1 + 1 = 2, \]and so $n^2$ divides $a^n - 1$. This makes both parts easy. For part (a), observe that any prime $p$ satisfies $\gcd(p,\varphi(p)) = \gcd(p,p-1) = 1$. For part (b), recall that the are infinitely many primes $p$ which are $2$ modulo $3$. Now let $n = 3p$; then \[ \gcd(n,\varphi(n)) = \gcd(3p,2p-2) = \gcd(p+2,2p-2) = \gcd(p+2,6) = 1, \]and so $n$ has property $P$.
kootrapali
16.06.2021 02:42
a) The problem is trivial if $n=2$. Otherwise, we have $n|a^n-1\implies a^n\equiv 1\text{(mod n)}$. By FLT, this implies $a\equiv 1\text{(mod n)}\implies v_n(a^n-1)=v_n(a-1)+v_n(n)\geq 2$, as desired. b) Let $n=p_1p_2$ for odd primes $p_1,p_2$ such that $(n,\phi (n))=1$. Then $a^{p_1p_2}\equiv 1\text{(mod }p_1p_2\text{)}$. Since $(n,\phi (n))=1$, we must have $a\equiv 1\text{(mod }p_1p_2\text{)}$. Then, $v_{p_1}(a^n-1)=v_{p_1}(a-1)+v_{p_1}(n)\geq 2$, and similarly $v_{p_2}(a^n-1)\geq 2$, so we're done.
SPHS1234
15.08.2021 21:04
We know that there are infinitely many twin primes $(p,p+2)$ and then showed that for all such twin primes $n=p(p+2)$ works....It's okay right? This does prove the infinititude....
insertionsort
14.04.2022 07:38
(a) Let $p$ be any prime. By Fermat's Little Theorem, $a \equiv a^p \equiv 1 \pmod p$. In particular, $a = kp + 1$ for some integer $k$. Then, \[a^p - 1 \equiv (kp + 1)^p - 1 \equiv 0 \pmod{p^2}\]by binomial expansion, as required. (b) We claim that all $n$ of the form $2p$ satisfy $P$, where $p$ is any odd prime. By Fermat's Little Theorem, \[a^2 \equiv (a^2)^p \equiv a^{2p} \equiv 1 \pmod{2p},\]so $a^2 = kp + 1$ for some integer $k$. Then, \[a^{2p} - 1 \equiv (kp + 1)^p - 1 \equiv 0 \pmod{p^2}\]by binomial expansion. All perfect squares leave a residue of $1$ modulo $4$, so \[a^{2p} - 1 \equiv (a^2)^p - 1 \equiv 1^p - 1 \equiv 0 \pmod 4.\]Since $p$ is odd, $4p^2 \mid a^{2p} - 1$, as required.
programmeruser
29.01.2023 05:18
a) For the sake of clarity, let $n = p$, where $p$ is prime.
If $p = 2$, then $2|a^2 - 1$ implies that $a$ is odd. Therefore, we need that $4|(a+1)(a-1)$. This is evident as $2|a+1$ and $2|a-1$.
Now assume that $p$ is odd. By Fermat's Little Theorem, $a^{p} \equiv a \pmod{p}$. However, $n|a^p - 1$ implies that $a^p \equiv 1 \pmod{p}$; therefore, $a \equiv 1 \pmod{p}$, or $p|a-1$.
Therefore, $v_p(a-1) > 0$. By LTE, $v_p(a^n - 1) = v_p(a-1) + v_p(p)$. Note that $v_p(a-1) \geq 1$ since $p|a-1$, and clearly $v_p(p) = 1$. Therefore, $v_p(a^p - 1) = v_p(a-1) + v_p(p) \geq 2$, which implies that $p^2 | a^p - 1$, as desired. $\square$
b) We claim that all $n = 3p$ work, where $p$ is a prime such that $p > 3$ and $p \equiv 2 \pmod{3}$. There are infinitely many such primes by Dirchlet.
First, we consider divisibility by $3$.
Note that $3|a^{3p} - 1 \implies a^{3p} \equiv 1 \pmod{3}$. Since $3-1=2$, and the order of a mod $3$ must divide this, the order is either $1$ or $2$. If the order is $2$ then $2|3p$, which is a contradiction since $p$ is odd. Therefore, the order of a mod 3 is $1$. Therefore, $a \equiv 1 \pmod{3}$. From here we can proceed in a similar way as a) to prove the given.
For divisibility by $p$, we can note that the order must divide $\gcd(3p, p-1) = \gcd(p-1, 3)$. This is $1$ since $p \equiv 2 \pmod{3}$, then we can proceed in a similar way as a), and we are done. $\square$