0

Show that $70$ divide $101^{6n} - 1$ for all $n$ natural numbers.

I tried to show that $101^{6n}$$ \equiv 1$ mod $70$.

Thanks for all. I got it.

Note that $70$ $=$ $7$.$5$.$2$

As $101^{ϕ(7)}$ $\equiv 1$ mod $7$, so $101^{6n}$ $\equiv 1$ mod $7$ (Euler Theorem)

and $101^{ϕ(2)}$ $\equiv 1$ mod $2$, so $101^{6n}$ $\equiv 1$ mod $2$ (Euler Theorem)

and $101$ $\equiv 1$ mod $5$, so $101^{6n}$ $\equiv 1$ mod $5$

Therefore, $101^{6n}$ $\equiv 1$ mod $70$.

wavilson ferreira
  • 101
  • Do you mean $101^{6n}$? – Arthur Jan 29 '18 at 15:07
  • @Dr.SonnhardGraubner I know it's very likely that the OP meant $101^{6n}$, but until we have confirmation, we shouldn't go in and change things like that. It introduces a rather large change to the question and it's just wrong in my opinion. At the very least, you should leave a comment and ask specifically whether what you did was correct. – Arthur Jan 29 '18 at 15:10

2 Answers2

3

Since $101 \equiv 1\;(\text{mod}\;10)$, it follows that $101^{6} \equiv 1\;(\text{mod}\;10)$.

Since $101$ is not a multiple of $7$, it follows, by Fermat's Little Theorem, that $101^6\equiv 1\;(\text{mod}\;7)$.

Then $101^6 - 1$ is a multiple of both $10$ and $7$, hence it's a multiple of $70$.

Since $101^6\equiv 1\;(\text{mod}\;70)$, it follows that $101^{6n}\equiv 1\;(\text{mod}\;70)$, as was to be shown.

quasi
  • 58,772
  • Isn't the third line due to the chinese remainder theorem ? – Lærne Jan 29 '18 at 15:15
  • It's simpler than that. If $x$ is a multiple of both $a$ and $b$, then it's a common multiple of $a$ and $b$, hence it's a multiple of the least common multiple of $a$ and $b$. Thus, if an integer is a multiple of both $10$ and $7$, it must be a multiple of $70$. – quasi Jan 29 '18 at 15:17
0

HINT: write your term $$101^{6n}-1$$ as $$\left(101^n-1\right) \left(101^n+1\right) \left(-101^n+101^{2 n}+1\right) \left(101^n+101^{2 n}+1\right)$$

Dr. Sonnhard Graubner
  • 95,283