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

Question

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.

Answer 1

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.