# $a^n-a + 1$ divisible by $n$

Problem. Given $$a$$ is a positive integer greater than 3, are there infinitely many positive integers $$n$$ satisfying $$a^n-a + 1$$ divisible by $$n$$?

• Interesting question. Have you tried anything yet? – Mohammad Zuhair Khan Oct 24 '18 at 8:30
• The case $a=2$ is popular, see here and the related links. – Dietrich Burde Oct 24 '18 at 8:48
• $n$ is not a prime number. It also must be odd. – Oldboy Oct 24 '18 at 18:16
• My original problem: Let $a\in\mathbb Z$ and $a>3$, prove that there exist infinitely many positive integers $n$ satisfying$$(n+a)\mid \left(a^n+1\right).$$ – Drona Oct 26 '18 at 19:54
• @Drona I think that you are making a big mistake. The statement $(n+a)|(a^n+1)$ is not equivalent to $n|(a^n-a+1)$. It's like saying that $(4+3)|14$ is equivalent to $4|(14-3)$. You should post the original problem. If you don't want to do it, I would like to do it. – Oldboy Oct 27 '18 at 8:39

$$N=a^n-a+1$$

$$a^{p_1} ≡ a \mod p_1$$

$$a^{p_2 } ≡a \mod p_2$$

$$(a^{p_1})^{p_2} ≡ a^{p_2} \mod p_1 ≡(a\ mod p_2) \mod p_1= k_1 p_1 + k_2 p_2 + a$$

$$a^{p_1p_2}=k_1 p_1 + k_2 p_2 +a$$

$$a^{p_1p_2}-a+1=k_1p_1 +k_2p_2 +1$$

If $$n=p_1p_2 | a^n-a+1$$ then we must have:

$$p_1p_2 | k_1p_1 + k_2p_2+1$$

So we have following linear equation:

$$k_1p_1 + k_2 p_2 = m p_1p_2-1$$

For certain value of $$p_1$$ and $$p_2$$ and m,there can be infinitely many solutions for $$k_1$$ and $$k_2$$. For example:

with $$p_1=5$$, $$p_2=7$$ and $$m=3$$ the equation has one solution like $$k_1=11$$ and $$k_2=7$$ and all other solutions can be found by:

$$k_1= 7 t + 11$$ and $$k_2= -5 t+7$$.

Now in first step problem reduces to:

Find n so that there exist a common divisor between $$n$$ and $$N=a^n-a+1$$.

For example for $$a=3$$, $$p_1=5$$ and $$p_2=7$$ we have:

$$3^{35}-3+1=105$$ and $$(35, 105)=5$$

In second step we must find m, $$k_1$$ and $$k_2$$ for certain amount of $$p_1$$ and $$p_2$$ so that $$(n, N)=n$$.

Relation $$a^{p_1p_2}=k_1 p_1 + k_2 p_2 +a$$ shows that $$a|k_1 p_1 + k_2 p_2$$; if $$k_1=u+1$$ and $$k_2=v-1$$, $$p_1= a .b+1$$ and $$p_2=a.c +1$$, i.e. $$p_1≡1\mod a$$ and $$p_2≡1\mod a$$, then:

$$k_1p_1+k_2p_2= M(a)$$

Or: $$a | k_1p_1+k_2p_2$$

We can see this in solution $$n=409\times 9831853$$ for $$a=6$$; $$409=48\times 6 +1$$ and $$9831853=1638642 \times 6 +1$$

This can help us in choosing a and primes $$p_1$$ and $$p_2$$

I see no reason for the lack of more solutions.