5
$\begingroup$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 \equiv a\cdot a^6 = a^7 \equiv a \bmod 7$.

So far I have that the largest $N$ for which all $ a^{13} \equiv a \bmod N$, is $N = 2\cdot 3\cdot 5\cdot 7\cdot 13 = 2730$

Can someone either put together an elegant proof of this, or find and prove a different limit?

$\endgroup$
  • 1
    $\begingroup$ Looks right. Any such $N$ has to be square-free. So we want the largest square-free $N$ such that $\lambda(N)$ (the Carmichael function) divides $12$. $\endgroup$ – André Nicolas May 14 '15 at 16:40
2
$\begingroup$

Suppose that $a^{13}\equiv a\pmod N$, for every $a\in\mathbb Z$, then for every prime $p$ deviding $N$ we have $a^{13}\equiv a\pmod p$, but we have a primitive root $g$ modulo $p$, hence $$ g^{12}\equiv1\pmod p $$ which means that $p-1|12$, so $p\in\{2,3,5,7,13\}$. Hence the prime factors of $N$ are from the above set. Now I prove that the number $N$ is squarefree...

Suppose not, then for some prime $p|N$ we have $a^{13}\equiv a\pmod {p^2}$ by choosing $a=p$ we get a contradiction, hence the number $N$ must be squarefree and by above arguments the number $2730$ is the largest possible value for $N$.

$\endgroup$
1
$\begingroup$

Putting in $a=2$, we get that $N$ divides $2^{13} - 2 = 2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$.

On the other hand, putting in $a=3$, we get that $N$ divides $3^{13} - 3 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 73$.

Hence $N$ must divide $2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730$.

$\endgroup$
  • $\begingroup$ So that's a good argument to show the limit... just need to add in the proof that 2730 is valid... $\endgroup$ – Joffan May 14 '15 at 16:44
1
$\begingroup$

Put $\ \color{#c00}{e = 13}\ $ below. $ $ For a simple proof of the theorem see this answer.

Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have $$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^{\large\color{#c00}{e}}\!-a\ \iff\ n\ is\ squarefree,\ \ and \ \ p\!-\!1\mid \color{#0a0}{e\!-\!1}\ \, for\ all \ primes\ \ p\mid n$$

The primes $\rm\,p\,$ such that $\rm\,p\!-\!1\mid\color{#0a0}{ 12}\,$ are $\,2,3,5,7,13\,$ so the largest such $\rm\,n\,$ is their product.

$\endgroup$
  • 1
    $\begingroup$ @Joffan It's a hint if you don't peek at the linked proof! In any case, this shows how the argument works in general. $\endgroup$ – Bill Dubuque May 14 '15 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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