0
$\begingroup$

Fermat's little theorem says that the congruence $a^p \equiv a (mod p)$ if $p$ is a prime number. $a^{n+1} \equiv a (mod n)$ works for all integers $a$ and some positive integers $n$, how can we characterize the positive integers $n$ for which $a^{n+1} \equiv a (mod n)$ holds?

$\endgroup$
7
  • 5
    $\begingroup$ You say a certain congruence works for all $a$ and some $n$ but do not give examples. Why not help readers by including the first few $n$ in your question? With a computer I find the only $n \leq 3000$ that work are 1, 2, 6, 42, and 1806. At oeis.org, this is A014117. $\endgroup$
    – KConrad
    Sep 18, 2014 at 13:04
  • 2
    $\begingroup$ The new title is incorrect, or based on faulty understanding: search online for "Carmichael number". $\endgroup$
    – Yemon Choi
    Sep 18, 2014 at 17:46
  • 2
    $\begingroup$ The question in its current form still seems to be off-topic, for the reasons given by those who voted to close. $\endgroup$
    – Yemon Choi
    Sep 18, 2014 at 17:49
  • 3
    $\begingroup$ The edited question makes all the earlier comments and answers incomprehensible. This is not a good way to proceed. $\endgroup$
    – Lucia
    Sep 18, 2014 at 17:53
  • 1
    $\begingroup$ Moreover this is a duplicate from mathoverflow.net/questions/37097/… $\endgroup$ Sep 19, 2014 at 9:32

2 Answers 2

10
$\begingroup$

This is one of Don Zagier's problems: http://www-groups.dcs.st-and.ac.uk/~john/Zagier/Problems.html First Day 1.

$\endgroup$
4
$\begingroup$

I claim that this holds for $n$ if and only if $n$ is square-free and for all prime divisors $p$ of $n$, we have $p-1\mid n$.

Let $n=p_1^{k_1}\cdots p_r^{k_r}$ be the prime factor decomposition of $n$. If at least one of the $k_i$ is greater than $1$, we see that $a:=p_1\cdots p_r$ is a counter-example, since its $(n+1)$-th power will be congruent to $0$ modulo $n$. Hence $n$ must necessarily be square-free: $n=p_1\cdots p_r$. Now for any $a\in\mathbb{Z}$, the congruence $a^{n+1}\equiv a\hspace{3pt}(\mathrm{mod}\hspace{3pt}n)$ holds by definition if and only if $n\mid a^{n+1}-a$, that is, if and only if for all $i=1,\ldots,r$, $p_i\mid a(a^n-1)$. So, for each $i=1,\ldots,r$, precisely one of the two statements $p_i\mid a$ and $p_i\nmid a \wedge \mathrm{ord}_{p_i}(a)\mid n$ must be satisfied, where $\mathrm{ord}_p$ denotes the multiplicative order modulo $p$. Choosing, for $i=1,\ldots,r$, $a_i$ to be a primitive root modulo $p_i$, we see that necessarily $p_i-1\mid n$ for all $i=1,\ldots,r$, and this is sufficient as well.

$\endgroup$
3
  • $\begingroup$ It is impossible for every prime $p$ dividing $n$ also $p-1|n$. Take the least prime divisor for example. $\endgroup$ Sep 18, 2014 at 13:39
  • $\begingroup$ What about $p = 2$? $\endgroup$
    – user19475
    Sep 18, 2014 at 13:41
  • $\begingroup$ @TimoKeller i missed this case,you are right. $\endgroup$ Sep 18, 2014 at 13:43

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