Fdtxjr

Problem: Prove that there are an infinite amount of positive square free integers $n$ such that $nmid2015^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.

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_1cdots p_k mid a^p_1cdots p_k - 1$ and

(ii) $p_k mid a^p_1cdots 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 $Pmid 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 $Pcdot p_k mid A - 1$, so $Pcdot p_k mid A^p_k - 1 = a^Pcdot 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 midmid 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, $rge 1$ and $p^rmidmid a - 1$, then $p^r+1midmid 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 + binomp2 m^2 p^2r + (textterms in higher powers of p).
$$
Since $p$ is an odd prime, $p$ divides $binomp2$, so
$$
a^p - 1 = p^r+1(m + (texta multiple of p^r)).
$$
Since $rge1$, that establishes the lemma.

Lemma $2$: If $p$ is a prime and $pmid a-1$, then $operatornamegcd(a - 1, dfraca^p-1a-1) = p$.

By Lemma $1$, if $p^kmidmid a-1$, then $p^k+1midmid a^p - 1$, so $pmidmid dfraca^p-1a-1$. Hence the GCD is a multiple of $p$.

On the other hand,
$$
fraca^p-1a-1 = 1 + a + a^2 +cdots + a^p-1.
$$
Reducing this $bmod a-1$, we have
$$
fraca^p-1a-1 equiv 1 + 1 + 1 +cdots + 1 equiv p pmoda-1.
$$
That is, there is some integer $t$ such that $dfraca^p-1a-1 = (a-1)t + p$, so
$p = dfraca^p-1a-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-1mid 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_1cdots p_k-1 mid a^Q - 1$, so
$$
p_1cdots p_k-1 mid a^P - 1 = (a^Q - 1) fraca^P - 1a^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 $dfraca^P - 1a^Q - 1$.
Writing
$$
fraca^P - 1a^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$, $dfraca^P - 1a^Q - 1$ is not divisible by $p_k-1^2$, so $dfraca^P - 1a^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 = 2cdot19cdot53$. Take $p_1 = 19$; then $19mid 2015 - 1$ and $19mid 2015^19 - 1$.
The lengthy argument above shows that $dfrac2015^19 - 12015 - 1$ is divisible by $19$, but not $19^2$. In fact, $$
frac2015^19 - 12015 - 1 = 19cdot 22186954931 cdot (texta 48text-digit prime).
$$
Let $p_2 = 22186954931$, so $p_2mid 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.