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?
-
$\begingroup$ dale- works for all n of the form 3^m. Just verify by induction!trying out with other prime factors of n... $\endgroup$– Somabha MukherjeeDec 21, 2011 at 8:24
-
$\begingroup$ I hope it's ok, I changed the title into something a bit more descriptive. $\endgroup$– Gjergji ZaimiDec 21, 2011 at 9:03
-
2$\begingroup$ A minor remark: The stipulation g.c.d(a,n)=1 is superfluous. If $n$ divides $a^n-1$, it can't share a nontrivial factor with $a$. $\endgroup$– Barry CipraDec 21, 2011 at 13:39
2 Answers
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.
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.