Question

Hello guys! Firstly, I'd like to start with a problem: Find all natural numbers n, for which n divides (10^n)-1. Then, I wanna generalize the statement as: Is it possible to find all solutions to the the statement: n divides (a^n)-1, where g.c.d(a,n)=1? Is there any method or algorithm at least, in this case?

Answer 1

The question for $a=10$ was investigated in

C. Cooper & R. E. Kennedy, "Niven Repunits and 10^n = 1 (mod n)" in 'The Fibonacci Quarterly' pp. 139-143 vol 27.2 May 1989

C. Smyth has a paper "The terms in Lucas sequences divisible by their indices" where a similar procedure is described for the general case $n|a^n-b^n$. The main theorem is as follows:

Theorem Suppose that $\gcd(a, b) = 1$. Then the elements of the set $\lbrace n | a^n\equiv b^n\pmod{n}\rbrace$ consist of those integers $n$ whose prime factorization can be written in the form $n = p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r}$ ($p_1 < p_2 < \cdots < p_r$ and all $k_i \geq 1$), where $p_i | a^{n_i} − b^{n_i}$ ($i = 1, \dots, r$), with $n_1 = 1$ and $n_i = p_1^{k_1} p_2^{k_2}\cdots p_{i-1}^{k_{i−1}}$ ($i = 2,\dots , r$).

This allows you to search recursively for allowed primes, and I doubt that there is a more elegant method for generating such numbers.

Answer 2

I would just add a short sentence to the above answer. Since you are only interested in the case when $b=1$ there is a very simple elementary characterization: $n|a^n-1$ if and only if $\mathrm{ord}_n(a)|n$. That also explains the comment above that $3^m|10^{3^m}-1$.

Unfortunately I think it also means that there is no good `formula' for the answer to your problem.