3
$\begingroup$

Problem: Prove that there are an infinite amount of positive square free integers $n$ such that $n\mid2015^n-1$

I have no idea how to solve this one and I haven't found any good results yet. Would be really nice if someone knew how to solve this problem. Thanks in advance.

$\endgroup$
  • $\begingroup$ Are you sure you want $2015^n$ and not, maybe, $2015^{n-1}$? $\endgroup$ – Dirk Mar 21 '19 at 12:22
  • $\begingroup$ @Dirk I had this in a test sometime ago and I'm pretty sure that it was $2015^n$. $\endgroup$ – someone Mar 21 '19 at 13:13
  • $\begingroup$ Can you give us a link? You know "seeing is believing". $\endgroup$ – Dietrich Burde Mar 21 '19 at 13:13
  • $\begingroup$ It is perhaps worth noting that finding $n\ge 2$ with $n\mid a^n-1$ is not always easy. For $a=2$ it is impossible, see this post. So let's first make abosultely sure that there is no typo. $\endgroup$ – Dietrich Burde Mar 21 '19 at 14:10
  • $\begingroup$ @DietrichBurde There's no link to the problem (if that was what you meant) as it was in a test and I'm very certain that there's no typo. $\endgroup$ – someone Mar 21 '19 at 19:29
7
$\begingroup$

Let $a$ be an integer which is odd and greater than $1$ such that $a - 1$ has an odd prime factor. (In particular, $2015$ is such an integer.) Then there exists an infinite sequence $p_1$, $p_2$, ... of distinct odd primes such that, for any $k \ge 1$, the following conditions hold:

(i) $p_1\cdots p_k \mid a^{p_1\cdots p_k} - 1$ and

(ii) $p_k \mid a^{p_1\cdots p_{k-1}} - 1$.

Condition (i) provides the squarefree values of $n$ asked for in the question; condition (ii) will be needed for the proof which is by induction on $k$.

For $k = 1$: Let $p_1$ be an odd prime factor of $a - 1$. Then $p_1 \mid a - 1$ (which is condition (ii)), so $p_1 \mid a^{p_1} - 1$ (which is condition (i)).

For $k \gt 1$: Let $P = p_1 \cdots p_{k-1}$ and let $A = a^P$; then, by induction (condition (i)), we have $P\mid A-1$. Suppose that $p_k$ is an odd prime other than $p_1,\ldots,p_{k-1}$ that divides $A-1$, thereby satisfying condition (ii). Then $P\cdot p_k \mid A - 1$, so $P\cdot p_k \mid A^{p_k} - 1 = a^{P\cdot p_k} - 1$, satisfying condition (i).

It remains only to show that a suitable prime $p_k$ always exists. That will take most of the rest of this long post.

First, some notation: When $p$ is a prime, $p^r \mid\mid m$ means that $p^r$ "exactly divides" $m$; that is, $p^r$ divides $m$, but $p^{r+1}$ does not.

Lemma $1$: If $p$ is an odd prime, $r\ge 1$ and $p^r\mid\mid a - 1$, then $p^{r+1}\mid\mid a^p - 1$.

Write $a - 1 = mp^r$, where $p$ does not divide $m$. Then $a = 1 + mp^r$ and $$ a^p = (1 + mp^r)^p = 1 + mp^{r+1} + \binom{p}{2} m^2 p^{2r} + (\text{terms in higher powers of }p). $$ Since $p$ is an odd prime, $p$ divides $\binom{p}{2}$, so $$ a^p - 1 = p^{r+1}(m + (\text{a multiple of }p^r)). $$ Since $r\ge1$, that establishes the lemma.

Lemma $2$: If $p$ is a prime and $p\mid a-1$, then $\operatorname{gcd}(a - 1, \dfrac{a^p-1}{a-1}) = p$.

By Lemma $1$, if $p^k\mid\mid a-1$, then $p^{k+1}\mid\mid a^p - 1$, so $p\mid\mid \dfrac{a^p-1}{a-1}$. Hence the GCD is a multiple of $p$.

On the other hand, $$ \frac{a^p-1}{a-1} = 1 + a + a^2 +\cdots + a^{p-1}. $$ Reducing this $\bmod a-1$, we have $$ \frac{a^p-1}{a-1} \equiv 1 + 1 + 1 +\cdots + 1 \equiv p \pmod{a-1}. $$ That is, there is some integer $t$ such that $\dfrac{a^p-1}{a-1} = (a-1)t + p$, so $p = \dfrac{a^p-1}{a-1} - (a-1)t$. Thus the GCD divides $p$.

Hence, the GCD is $p$.

Finally, return to the induction step. Let $Q = P/p_{k-1}$; then condition (ii) of the induction hypothesis says that $p_{k-1}\mid a^Q - 1$; likewise all the preceding $p_i$ (if any) divide $a^Q - 1$ by condition (i) of the preceding induction step (if any). Thus $p_1\cdots p_{k-1} \mid a^Q - 1$, so $$ p_1\cdots p_{k-1} \mid a^P - 1 = (a^Q - 1) \frac{a^P - 1}{a^Q - 1}. $$ By Lemma $2$, the GCD of the two factors on the right is $p_{k-1}$, so none of the other $p_i$ divide $\dfrac{a^P - 1}{a^Q - 1}$. Writing $$ \frac{a^P - 1}{a^Q - 1} = 1 + a^Q + a^{2Q} + \cdots + a^{(p_{k-1}-1)Q}, $$ one sees that this factor is the sum of $p_{k-1}$ odd terms, and thus odd, and $\gt p_{k-1}$, since $a \gt 1$. By Lemma $1$, $\dfrac{a^P - 1}{a^Q - 1}$ is not divisible by $p_{k-1}^2$, so $\dfrac{a^P - 1}{a^Q - 1}$ cannot be a power of $p_{k-1}$. Thus there is some odd prime $p_k$ that divides it (and thus $a^P - 1$) which is distinct from the preceding $p_i$. That completes the proof.

A numerical example may help to clarify the process. Let $a = 2015$, so $a-1 = 2\cdot19\cdot53$. Take $p_1 = 19$; then $19\mid 2015 - 1$ and $19\mid 2015^{19} - 1$. The lengthy argument above shows that $\dfrac{2015^{19} - 1}{2015 - 1}$ is divisible by $19$, but not $19^2$. In fact, $$ \frac{2015^{19} - 1}{2015 - 1} = 19\cdot 22186954931 \cdot (\text{a }48\text{-digit prime}). $$ Let $p_2 = 22186954931$, so $p_2\mid 2015^{19} - 1$ and $19 p_2 \mid 2015^{19 p_2} - 1$. To no one's surprise, and as has been proved, $2015^{19 p_2} - 1$ will contain at least one new odd prime factor that can be taken as $p_3$. And so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.