3
$\begingroup$

I'm looking for a hint regarding the following proof, I've played with a few approaches, mainly rewriting the conditions as congruences and equations and toying with the algebra, but am having trouble connecting the dots. Thanks! -

Consider $n = p_1p_2 \dotsc p_s$ with $p$ primes, such that $\forall_i \ \ (p_i-1) \ | \ (n-1)$.

Show that $a^n \equiv a \ (\text{mod}\ n)$ for all $a$ ($1 \leq a \leq n -1$)

$\endgroup$
7
  • $\begingroup$ can you show $a^n \equiv a \mod p_1$? $\endgroup$
    – mdave16
    Commented Mar 8, 2017 at 23:51
  • 1
    $\begingroup$ I think that hint should take you all the way there, but I'll post a complete solution w/ details tomo if you haven't managed. - Try and beat me to it :P $\endgroup$
    – mdave16
    Commented Mar 8, 2017 at 23:53
  • 2
    $\begingroup$ $\,p\mid a^n-a\,$ is clear if $\,p\mid a,\,$ else apply little Fermat to show $\,p\mid a^{n-1}-1.\,$Then since each $p_i$ divides $\,a^n-a\,$ so too does their lcm = product. The converse holds too, see here. $\endgroup$
    – Bill Dubuque
    Commented Mar 8, 2017 at 23:54
  • 2
    $\begingroup$ I think these numbers are called Carmichael numbers. For example, $561 = 3 \times 11 \times 17$, and $560$ is a multiple of $2,10,16$. These numbers actually have nicer properties than the above. For example, the third Carmichael number is $1729$, which rings a bell. $\endgroup$
    – Sarvesh Ravichandran Iyer
    Commented Mar 9, 2017 at 0:03
  • $\begingroup$ @астон That is mentioned in the link I gave. $\endgroup$
    – Bill Dubuque
    Commented Mar 9, 2017 at 0:46

1 Answer 1

Reset to default
1
$\begingroup$

So this is what I arrived at:

By FLT $\rightarrow$ $\forall_i \forall{a} \ (p_i \mid a^{p_i -1} -1)$. Because we know that $(p_i - 1) \mid (n-1)$, we have that $p_i \mid a^{n-1} - 1$. Since the relation holds for all $p_i$, then it also holds for their product $n$. Therefore, $n \mid a^{n-1} - 1$.

This gives $a^{n-1} \equiv 1 \ (\text{mod} \ n)$. Multiplying by $a$ on both sides, we get $a^{n} \equiv a \ (\text{mod} \ n)$, as we wanted.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .