0

I have the following task:

exactly one of the two Numbers $n$ and $n^6+6$ is divisible by 7.

My first thought was to use induction but $n \in \mathbb{Z}$ so I have to find another way. Any Hints? Maybe showing that $n$ is congruent to $n^6+6$ mod 7?

JonDoeMaths
  • 145
  • 1
    Hint: $2^3 \equiv 1 \pmod{7}$ and $3^3 \equiv -1 \pmod{7}$. – dxiv Nov 16 '16 at 18:06
  • 5
    Do you know Fermat's little theorem? – studiosus Nov 16 '16 at 18:09
  • Since $7$ is given concretely, you can check that $n^6+6$ is divisble by $7$ for $n=1,2,3,4,5,6$. You can conclude with elementary modular-arithmetic that $n^6+6$ is divisble by $7$, whenever $n$ is an integer not divisble by $7$. – Peter Nov 16 '16 at 18:23
  • $n$ and $n^6+6$ cannot be congruent modulo $7$. This would contradict the claim that EXACTLY one of the numbers $n$ and $n^6+6$ is divisible by $7$ – Peter Nov 16 '16 at 18:28

2 Answers2

2

Solution without Fermat's Little Theorem, but a bit more arithmetic:

Any integer $n$ can be written as $7k+r$ with $k\in\mathbb{Z}$ and $r\in\mathbb{Z}_7$

If $r=0$ then $n$ is divisible by $7$, otherwise we will show that $n^6+6$ is divisible by $7$.

$(7k+r)^6+6=r^6+6\mod7$

We then have to check each $r\in\{1,2,3,4,5,6\}$

crb233
  • 392
  • 1
    For a shortcut, it's enough to check that $n^3 \equiv \pm 1 \pmod{7}$ if $n \not \equiv 0 \pmod{7}$ which reduces the list of tries to $(\pm 2)^3 = \pm 1 \pmod{7}$ and $(\pm 3)^3 = -1 \pmod{7}$. – dxiv Nov 16 '16 at 18:32
1

By Fermat's Little Theorem (Link), for $a\not\equiv0 \pmod p$, $$ a^{p-1} \equiv 1 \pmod p.$$

Let $p=7$.

If $n$ is not divisible by 7, we have $$n^6 \equiv 1 \pmod 7,$$ and therefore $$n^6 + 6 \equiv 0 \pmod 7.$$

If $n$ is divisible by 7, clearly $$n^6 +6 \equiv 6 \pmod 7.$$

Jared N
  • 331