5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ dale- works for all n of the form 3^m. Just verify by induction!trying out with other prime factors of n... $\endgroup$ Dec 21, 2011 at 8:24
  • $\begingroup$ I hope it's ok, I changed the title into something a bit more descriptive. $\endgroup$ Dec 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$ Dec 21, 2011 at 13:39

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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