Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
dale- works for all n of the form 3^m. Just verify by induction!trying out with other prime factors of n... –  Somabha Mukherjee Dec 21 '11 at 8:24
    
I hope it's ok, I changed the title into something a bit more descriptive. –  Gjergji Zaimi Dec 21 '11 at 9:03
2  
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$. –  Barry Cipra Dec 21 '11 at 13:39
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.