# Prove that $2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$

I am utterly new to modular arithmetic and I am having trouble with this proof.

$$2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$$

It's because $2+5=3+4=7$, but it's not so clear for me with the presence of powers.

Maybe some explanation would help.

EDITED Some serious typo

EDIT Since some arguments against it appear here is : WolframAlpha

EDIT Above is incorrect. I appreciate proofs that it is wrong. Sorry for others.

-
It's because 2+5=3+4=7. That is not at all obvious to me. –  anon Apr 5 '13 at 23:43
One obvious thing to do is to simplify the bases modulo $7$, because $a \equiv b \bmod 7$ implies $a^n \equiv b^n \bmod 7$. –  Hurkyl Apr 5 '13 at 23:52
A less obvious thing to do (but it becomes obvious with more experience) is to simplify the exponents modulo $6$, because $a^{\varphi(7)} \equiv 1 \bmod 7$ when $\gcd(a,7) = 1$, and so $a^{\varphi(7) x + y} \equiv a^y \bmod 7$. –  Hurkyl Apr 5 '13 at 23:53
The problem that you put into Wolfram Alpha and the problem that you posted here are different. –  Christopher A. Wong Apr 6 '13 at 0:57
@700resu: In the original question, typo and all, both sides are easily congruent to $0$. With the change, that is no longer true. (Alpha is irrelevant, a glance shows it is true.) –  André Nicolas Apr 6 '13 at 0:57

First recall that as $7$ is prime, then $x^6 = 1 \pmod{7}$. Now, we have $$2222 = \begin{cases} 2 \pmod{6} \\ 3 \pmod{7} \end{cases}, \quad 3333 = 1 \pmod{7}$$ $$4444 = -1 \pmod{7}, \quad 5555 = \begin{cases} 5 \pmod{6} \\ 4 \pmod{7} \end{cases}$$ Then we can reduce each side of the equation to $$3^5 + 4^2 = 1^5 + (-1)^2 \pmod{7}$$ Then the LHS is $0$ but the RHS is $2$, so the statement is false.

EDIT: For reference, I'm testing the conjecture $2222^{5555} + 5555^{2222} = 3333^{5555} + 4444^{2222}$.

-
I don't think this answer is correct: how the huge exponent $\,5555\,$, for example, is shrinked to $\,5\,$ ? –  DonAntonio Apr 6 '13 at 0:49
Because $x^6 = 1 \pmod{7}$ for all $x$, so we can reduce all the exponents to their value mod $6$. –  Christopher A. Wong Apr 6 '13 at 0:50
@ChristopherA.Wong: $x^6\not\equiv 1 \pmod 7$ when $x\equiv 0 \pmod 7$, not that it is relevant in this particular case. –  Henning Makholm Apr 6 '13 at 1:29
Ok, now I understand what you did, @ChristopherA.Wong: you worked also modulo $\,\phi(7)=6\,$... –  DonAntonio Apr 6 '13 at 1:38
@HenningMakholm, ah yes, I forget about that sometimes. While it didn't matter in this case, I had actually forgotten myself. –  Christopher A. Wong Apr 6 '13 at 1:40

$$2222=11\cdot202=22\cdot 101=101\pmod 7\\5555=11\cdot505=55\cdot 101=-101\pmod 7\\3333=11\cdot 303=33\cdot 101=(-2)\cdot 101\pmod 7\\4444=11\cdot404=44\cdot 101=2\cdot101\pmod 7$$

Well, now add modulo $\,7\,$ both sides of your equation...:)

Added: By the way, note that $\,101=3\pmod 7\,$ , so again doing arithmetic modulo $\,7\,$ we indeed get

\begin{align*}2222&=&3\\5555&=-3=&4\\3333&=-2\cdot 3=-6=&1\\4444&=2\cdot 6=&-1\end{align*}

-

See cycles.

1. $2222^6 \equiv 1\pmod{7}$ and $5555\equiv 5\pmod{6}$ then $2222^{5555}\equiv 2222^5\pmod{7}\equiv 5\pmod{7}$
2. $5555^3 \equiv 1\pmod{7}$ and $2222\equiv 2\pmod{3}$ then $5555^{2222}\equiv 5555^2\pmod{7}\equiv 2\pmod{7}$

left hand $= 5 + 2 \equiv 0\pmod{7}$

1. $3333^1 \equiv 1\pmod{7}$ and $5555\equiv 0\pmod{1}$ then $3333^{5555}\equiv 3333^1\pmod{7}\equiv 1\pmod{7}$

2. $4444^1 \equiv 1\pmod{7}$ and $2222\equiv 0\pmod{1}$ then $4444^{2222}\equiv 4444^1\pmod{7}\equiv 1\pmod{7}$

right hand $= 1 + 1 \equiv 2\pmod{7}$

$2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$ is incorrect.

You can check with bc program:

bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type warranty'.
2222^5555 % 7
5
5555^2222 % 7
2
3333^5555 % 7
1
4444^2222 % 7
1
`
-

First, you can change it to $3^{5555} + 4^{2222} \equiv 1^{5555} + 6^{2222} \pmod{7}$.

Then, notice that $3^6 \equiv 1 \pmod{7}$, $4^3 \equiv 1 \pmod{7}$, and $6^2 \equiv 1 \pmod{7}$. You can shrink the exponents to $3^5 + 4^2 \equiv 1 + 1 \pmod{7}$

From there, it's just computation: $$3^5 + 4^2 \equiv 1 + 6^0 \pmod{7}$$ $$243 + 16 \equiv 2 \pmod{7}$$ $$259 \equiv 2 \pmod{7}$$ $$0 \not\equiv 2 \pmod{7}$$

So it's false after all (I misread the exponents at first, sorry).

Since you're new to modular arithmetic, this may not be clear, but for all $x \ne 0$, $x^6 \equiv 1 \pmod{7}$. See Euler's totient theorem.

EDIT: Wow I'm sloppy today. Sorry. :\

-
You seem to believe that $\,2222=1\pmod 7\,$ but this is not so: $\,2222=3\pmod 7\,$ ... –  DonAntonio Apr 6 '13 at 0:06
@DonAntonio: How do you infer such a belief? As far as I can see the $2222$ as a base does correctly become 3 -- on the other hand, the $2222$ exponent is correctly reduced to $2$ (modulo 6). –  Henning Makholm Apr 6 '13 at 0:11
By looking to the first equation, @HenningMakholm: I'm trying to understand where that $\,1^{5555}\,$ on the right hand came from... –  DonAntonio Apr 6 '13 at 0:16
Of course, my belief is reinforced by the fact that I got a "true" value to the OP's claim, whereas Henry got a false one. Clearly, at least one of us is wrong...and by the life of me it could be myself. –  DonAntonio Apr 6 '13 at 0:17
@DonAntonio: $1^{5555}$ comes from $3333^{5555}$ in the question, and $3333=476\times 7 + 1$. –  Henning Makholm Apr 6 '13 at 0:22