2
$\begingroup$

As the title says, prove that $n^{17} \equiv n \;(\text{mod}\; 510)$. I know that you need to use the fact that $510 = 2\cdot 3\cdot 5\cdot 17$, but I can't figure out how. I've found a similar question on this forum, but can't make any sense out of the answer

$\endgroup$
  • 2
    $\begingroup$ Do you know that $n^{17}$ is congruent to $n$ modulo $2$, $3$, $5$, and $17$ separately? $\endgroup$ – Lubin Feb 17 '15 at 4:48
2
$\begingroup$

You would need Fermat's little theorem which states that for any natural $a$ and a prime $p$, $p$ divides $a^p - a$.

$n^{17} - n = n(n-1)(n+1)(n^2+1)(n^4+1)(n^8+1).$

Now note that:

  1. $n(n-1) = n^2 - n$.
  2. $n(n-1)(n+1) = n^3 - n$.
  3. $n(n-1)(n+1)(n^2 + 1) = n^5 - n$.
  4. $n(n-1)(n+1)(n^2+1)(n^4+1)(n^8+1)=n^{17} - n.$

Can you finish the proof?

$\endgroup$
  • 1
    $\begingroup$ Ah, I think I see it this way. Using FLT, we show that 2, 3, 5, and 17 divide $n^{17} - n$. Thus, 510 divides it, so $n^{17} \equiv n \;(\text{mod}\; 510)$ $\endgroup$ – wlyles Feb 17 '15 at 5:58
5
$\begingroup$

Note that $\,p_i\!-1 = 1,2,4,16\mid 16 = e\!-\!1,\,$ so the following theorem $(\Leftarrow)$ applies

Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree, \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n\qquad$$

Proof $\ \ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: \color{#c00}{a^{p-1} \equiv 1}\ \ ( mod\ p),\:$ by little Fermat, i.e.

$$\rm e\!-\!1 = k(p\!-\!1)\,\Rightarrow\, a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\qquad\qquad $$

$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then $\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$

$(2)\ \ $ Let $\rm\ a\ $ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$ Thus $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ but $\rm\:p\nmid a,\:$ thus $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ the order of $\rm\ a\,\ (mod\ p).\quad$ QED

$\endgroup$
1
$\begingroup$

Well, the post you mention outlines the process somewhat. Apply Fermat's Little Theorem to acquire the following:

$n^{17} \equiv n$ (mod 17)

Now let's establish $n^{17} \equiv n$ (mod 2). This is pretty simple: $n^{17}-n = n(n^{16}-1)$, and either $n$ will be even or $n^{16}-1$ will be even. Hence, $2\, |\, n^{17} - n$, and so $n^{17} \equiv n$ (mod 2).

We note that $17 \equiv 1$ (mod 2), and so from a generalization of Fermat's Little Theorem, $n^{17} \equiv n^1$ (mod 3).

We note that $17 \equiv 1$ (mod 4), and so from the same generalization, $n^{17} \equiv n^1$ (mod 5).

Now we have all the ingredients. Since $2 \,|\, n^{17} - n$, $3\, | \,n^{17} - n$, $5\,|\,n^{17}-n$, and $17 \,|\, n^{17}-n$, it must be that $510 = 2 \cdot 3 \cdot 5 \cdot 17 \,| \,n^{17} - n$.

$\endgroup$

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.