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

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

• Work modulo $2016$. – Arthur Aug 7 '16 at 16:17
• @Artur, Ok. How do I found out what $2^{2018} \mod 2016$ is though? Without using a calculator. – Kamil Aug 7 '16 at 16:26
• The Chinese remainder theorem plus Euclid's theorem is the standard approach. – Arthur Aug 7 '16 at 16:29
• 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? – Kamil Aug 7 '16 at 16:52
• 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. – Arthur Aug 7 '16 at 17:01

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$

• My edit was to capitalize Fermat. Good answer. – DanielWainfleet Aug 7 '16 at 16:27
• We can use $$2^3\equiv1\pmod7,2018\equiv2\pmod3$$ – lab bhattacharjee Aug 7 '16 at 16:28
• @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. – Bill Dubuque Aug 7 '16 at 17:20

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?

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

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

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

• Sorry, your notation confuses me. I don't really understand all your steps. What is $K$ ? – Kamil Aug 7 '16 at 21:03
• @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. – Bill Dubuque Aug 7 '16 at 21:09
• @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}$$ – Bill Dubuque Aug 7 '16 at 21:16
• 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$. – Kamil Aug 7 '16 at 21:31
• @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),\,$ – Bill Dubuque Aug 7 '16 at 21:55