1
$\begingroup$

Let $n$ be an integer not divisible by $3$. Show that $n^7 ≡ n (\mod 63)$.

I know that we can split $63$ into $3^2 \cdot 7$ So we have $n^7=n (\mod 7\cdot3^2)$

$n^7=n (\mod 3^2)$ and $n^7 = n (\mod 7)$

And I am stuck how to go about solving this question after this

$\endgroup$
  • 2
    $\begingroup$ Title: not a theory, but a theorem (a little one). $\endgroup$ – Dietrich Burde Oct 16 '17 at 18:39
  • $\begingroup$ @user236182 "Let $n$ be an integer not divisible by $3$" $\endgroup$ – Carl Schildkraut Oct 16 '17 at 18:41
  • $\begingroup$ By binomial theorem, if $3\nmid n$, then $n^6\equiv (3k\pm 1)^6\equiv 1\pmod{9}$. $\endgroup$ – user236182 Oct 16 '17 at 18:45
2
$\begingroup$

Hint: If $3\nmid n$, we can say $n^6\equiv 1 \bmod 9$ (why?) If $7\nmid n$, $n^6\equiv 1\bmod 7$ (why?) What happens if $7|n$?

$\endgroup$
0
$\begingroup$

$$n^7-n=n(n^3-1)(n^3+1)=(n-1)n(n+1)(n^2-n+1)(n^2+n+1).$$ Now, it's obvious that $(n-1)n(n+1)$ is divisible by $3$.

Let $n=3k-1$, where $k$ be a natural number.

Thus, $n^2-n+1$ is divisible by $3$.

Let $n=3k+1$, where $k$ be a natural number.

Thus, $n^2+n+1$ is divisible by $3$,

which says that $n^7-n$ is divisible by $9$.

Also, $n^7-n$ is divisible by $7$ for all integer $n$ by the Fermat's little theorem, which says that it's divisible by $7$ for all integers $n$, which not divisible by $3$ and we are done!

$\endgroup$
0
$\begingroup$

Let $n$ be $n=3m\pm1$ $$(3m\pm1)^7\equiv (3m\pm1)\pmod{63}\iff(3m\pm1)((3m\pm1)^6-1)\equiv0\pmod{63}$$

The $LHS$ is divisible by $7$, by either $3m\pm1$ is a multiple of $7$ or because of FLT in the second factor (i.e. $(3m\pm1)^6-1\equiv0\pmod7$ ).

Besides it is clear that $(3m\pm1)^6-1\equiv 0\pmod9$

$\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.