2
$\begingroup$

Prove that $\gcd(2016, 2017^{2017} + 2018^{2018}) = 1$.

I don't know how to do this. I tried different strategies, they all leading me nowhere. I tried to write $2017^{2017} + 2018^{2018}$ as $2017 x + 2017y$, where $x, y$ are some integers, but I don't know how.

Also, tried proving by contradiction but I think that's the wrong direction too.

Any help/hints?

EDIT: I'm suppose to find this without using a calculator. So I don't know the prime factorization etc.

Based on Arthur's hint, I have $$ (2017^{2017} + 2018^{2018}) \mod 2016 \\ = (1 + 2^{2018} \mod 2016) \mod 2016. $$ I now still need to prove that $$2^{2018} \mod 2016 = 0. $$

$\endgroup$
  • 1
    $\begingroup$ Work modulo $2016$. $\endgroup$ – Arthur Aug 7 '16 at 16:17
  • $\begingroup$ @Artur, Ok. How do I found out what $ 2^{2018} \mod 2016$ is though? Without using a calculator. $\endgroup$ – Kamil Aug 7 '16 at 16:26
  • $\begingroup$ The Chinese remainder theorem plus Euclid's theorem is the standard approach. $\endgroup$ – Arthur Aug 7 '16 at 16:29
  • $\begingroup$ Arthur, is $2^{2018} \mod 2016$ equivalent to $2^{2018} \mod 63$ ? What system do I set up so I can use Chinese remainder theorem? $\endgroup$ – Kamil Aug 7 '16 at 16:52
  • $\begingroup$ No, $2^{2018}\mod{2016}$is equivalent to $2^{2018}\mod{63}$ and $2^{2018}\mod{32}$ simultaneously. That's what the Chinese remainder theorem tells you. $\endgroup$ – Arthur Aug 7 '16 at 17:01
3
$\begingroup$

The primes dividing $2016$ are $2,3$ and $7$. So to solve our problem we must show neither of these primes divides $2017^{2017}+2018^{2018}$.

Clearly $2017^{2017}+2018^{2018}$ is odd.

Notice $2017^{2017}+2018^{2018}\equiv 1^{2017}+(-1)^{2018}\equiv 2 \bmod 3$

Finally, notice $2017^{2017}+ 2018^{2018}\equiv 1^{2017}+2^{2018}\bmod 7$.

By Fermat's theorem $2^{6}\equiv 1 \bmod 7$, so $1^{2017}+2^{2018}\equiv 1+(2^{336})^6\times 2^2\equiv 1+2^2\equiv 5 \bmod 7$

$\endgroup$
  • $\begingroup$ My edit was to capitalize Fermat. Good answer. $\endgroup$ – DanielWainfleet Aug 7 '16 at 16:27
  • $\begingroup$ We can use $$2^3\equiv1\pmod7,2018\equiv2\pmod3$$ $\endgroup$ – lab bhattacharjee Aug 7 '16 at 16:28
  • $\begingroup$ @lab Or we can use $\ 2^{\large 5+6K}\equiv 2^{\large 5}\pmod{2016}\,$ without requiring any factorization of the modulus - see my answer. $\endgroup$ – Bill Dubuque Aug 7 '16 at 17:20
1
$\begingroup$

Clearly, $ 2017^{2017} + 2018^{2018}$ is odd and the highest power of $2$ in $2016$ is $5, 2016=2^5\cdot63$

So, it sufficient to show $(63,2017^{2017} + 2018^{2018})=1$

As $2017\equiv1\pmod{2016},2017^{2017}\equiv1\pmod{2016},2017^{2017}\equiv1\pmod{63}$

Again, $2018\equiv2\pmod{63}, 2018^{2018}\equiv2^{2018}$

Now $2^6\equiv1\pmod{63}$ and $2018\equiv2\pmod6\implies2^{2018}\equiv2^2\pmod{63}$

$\implies2017^{2017} + 2018^{2018}\equiv1+2^2\pmod{63}$

Can you take it from here?

$\endgroup$
  • $\begingroup$ How do you see that $2016 = 2^5 \cdot 63$ ? $\endgroup$ – Kamil Aug 7 '16 at 16:33
  • 1
    $\begingroup$ @Kamil, By continuing division by $2$ until the result is odd $\endgroup$ – lab bhattacharjee Aug 7 '16 at 16:34
1
$\begingroup$

Hmmph. The two things that jump at me are:

1) $2017^{2017} = (2016 + 1)^{2017} \equiv 1 \mod 2016$

$2018^{2018} = (2016 + 2)^{2018} \equiv 2^{2018} \mod 2016$

And

2) $2017^{2017} + 2018^{2018}$ is odd. So $2 \not \mid \gcd(2016, 2017^{2017}+2018^{2018} )$.

Therefore

$\gcd(2016=63*2^5, 2017^{2017}+2018^{2018}) = \gcd(63, 1 + 2^{2018})$

Which should be solvable by FLT

By FLT $2^{\phi(63)} = 2^{\phi(3^2)\phi(7)} = 2^{3*2*6}= 2^{36} \equiv 1 \mod 63$

So $2018 \equiv 2 \mod 36$ so $2^{2018}\equiv 2^2 = 4 \mod 63$.

So $1 + 2^{2018} \equiv 4 = 1 = 5 \mod 63$.

So $\gcd(2016, 2017^{2017} + 2018^{2018})= \gcd(63, 5) = 1$.

$\endgroup$
1
$\begingroup$

${\rm mod}\,\ 2016\!:\ 2^{11}\!=2048\equiv 2^{\large 5}\! \overset{\,\times\, {\large 2^{\Large 6}}}\Rightarrow 2^{\large 17}\!\equiv 2^{\large 11}\!\equiv 2^{\large 5}\ldots\Rightarrow \color{#c00}{2^{\large 5+6K}\!\equiv 2^{\large 5}}\, $ for all $K\ge 0\:$ so

$$ \color{#0a0}{2^{\large 2018}}\equiv\, 2^{\large 3}\, \color{#c00}{2^{\large 5 + 6\cdot 335}}\equiv 2^{\large 3}\,\color{#c00}{2^{\large 5}}\equiv \color{#0a0}{2^{\large 8}}$$

$$\Rightarrow\ \ N :=\, 2017^{\large 2017}\!+2018^{\large 2018}\equiv\, 1^{\large 2017}\!+\color{#0a0}{2^{\large 2018}}\equiv 1+\color{#0a0}{2^{\large 8}}\equiv\, \color{#90f}{257}\qquad $$

Thus Euclidean algorithm $\,\Rightarrow (2016,N) = (2016,\, N\, {\rm mod}\ 2016) = (2016, \color{#90f}{257}) = 1$

$\endgroup$
  • $\begingroup$ Sorry, your notation confuses me. I don't really understand all your steps. What is $K$ ? $\endgroup$ – Kamil Aug 7 '16 at 21:03
  • $\begingroup$ @Kamil $K$ is any natural. If you keep iterating what I did (i.e. scaling prior congruence by $\,2^6),\,$ then you get an inductive proof of the red congruence. $\endgroup$ – Bill Dubuque Aug 7 '16 at 21:09
  • $\begingroup$ @Kamil Below is the inductive step (where the red congruence is true by induction hypothesis) $${2^{\large 5+6(K+1)}}\equiv \color{#c00}{2^{\large 5+6K}}2^{\large 6}\equiv \color{#c00}{ 2^{\large 5}}2^{\large 6}\!\equiv 2^{\large 11}\!\equiv 2^{\large 5}$$ $\endgroup$ – Bill Dubuque Aug 7 '16 at 21:16
  • $\begingroup$ But you lost me already at the first arrow you wrote. Why do you start with $2^{11}$ ? I want to compute $2^{2018} \mod 2016$. I understand this equals $(2^3 2^{5 + 6 \cdot 335}) \mod 2016$. So using rules for modulo arithmetic this equals $(( 2^3\ \text{mod} \ 2016) \cdot (2^{5 + 6 \cdot 335} \ \text{mod} \ 2016)) \mod 2016$. $\endgroup$ – Kamil Aug 7 '16 at 21:31
  • $\begingroup$ @Kamil Let $\,P(k)\,$ be $\,2^{\large 5+6K}\!\equiv 2^{\large 5}.\,$ First arrow is $\,P(1)\Rightarrow P(2)\,$ i.e. $\,2^{\large 11}\!\equiv 2^{\large 5}\!\Rightarrow2^{\large 17}\!\equiv 2^{\large 5}.$ The proof is a special case of the proof $\,P(k)\Rightarrow P(k+1)\,$ that I gave in my prior comment. The idea of the inductive step is that multplying $\,P(k)\,$ by $\,2^{\large 6}\,$ yields $\,P(k+1),\,$ $\endgroup$ – Bill Dubuque Aug 7 '16 at 21:55

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.