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

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.

• Are you sure you want $2015^n$ and not, maybe, $2015^{n-1}$? – Dirk Mar 21 '19 at 12:22
• @Dirk I had this in a test sometime ago and I'm pretty sure that it was $2015^n$. – someone Mar 21 '19 at 13:13
• Can you give us a link? You know "seeing is believing". – Dietrich Burde Mar 21 '19 at 13:13
• 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. – Dietrich Burde Mar 21 '19 at 14:10
• @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. – someone Mar 21 '19 at 19:29

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.