# Solving a (tricky) arithmetic congruence equation in the general case

Out of sheer curiosity, I am looking for the solutions of the congruence equation :

$n^{n+km} \equiv n$ mod m for every k natural integer

where $k,n,m \in N$

where m=$p_1^{\alpha_1}p_2^{\alpha_2} . . .p_n^{\alpha_n}$, the $p_i$ are (distinct) primes and the ${\alpha_i}$ are integers >=1.

In the case it's not clear enough k isn't a fixed parameter. In other words, for fixed m, for n to be a solution, it has to be a solution of the equation for every k>=0 integer. If it works for every k except k=0 or whatever integer, it is not a solution.

I don't know if there is an "easy" solution to this problem, but I think the way to go about this is to decompose m in prime numbers.

For example, if m=p where p is a prime, the only solution is 1 and it is fairly easy to prove.

I have found other patterns with numeric simulations, sometimes obvious, sometimes a bit less obvious, but have never been able to prove anything other than the m=p case...

Some patterns I have found but not proven and/or sometimes don't work:

(note : I removed the solution "1" as a convention in these, since it is trivial)

****if $m=p^{2n}$ then S={$1+kp^n,k \in N*,k<=p^n-1$} and Card(S)=$p^n$-1, where S is the set of solutions.

Note : From numeric simulations this seem to work pretty well at first, but I also found additionnal solutions for high powers of 2 which were not of this form, so this is not exhaustive (and perhaps not even true)

****if m=pp', p and p'>3, then S={$1+kpp',k \in N*, k<=p'-1, 1+k'pp'+p'p'', k'<=p'-1$} and Card(S)=2p', where p'' is the solution of py-p'x=1 for p' mod p.

****The previous case suggest the general solution involve the use of the totient function $\phi$

The general case would involve solving it with :

m=$p_1^{\alpha_1}p_2^{\alpha_2} . . .p_n^{\alpha_n}$ where the $p_i$ are (distinct) primes.

But as I said I have no idea how long it would take, so I'd be very grateful even for partial answers like solutions and the proof for what I assume to be the next simplest case $m=p^2$.

Any idea ? Thanks for trying !