1. ## congruence

a) If a^p = b^p mod p, prove that a = b mod p

b) If a a = b mod p, prove that a^p = b^p mod p

2. #1: $\displaystyle b \equiv b^{p} \equiv a^{p} \equiv aa^{p - 1} \equiv \hdots \ (\text{mod } p)$ (Hint: Fermat's theorem)

#2: You can use the fact that if $\displaystyle a \equiv b \ (\text{mod }p)$ and $\displaystyle c \equiv d \ (\text{mod }p)$ then $\displaystyle ac \equiv bd \ (\text{mod } p)$. Then it's just a matter of considering $\displaystyle c = a$ and $\displaystyle d = b$

3. Originally Posted by o_O
#1: $\displaystyle b \equiv b^{p} \equiv a^{p} \equiv aa^{p - 1} \equiv \hdots \ (\text{mod } p)$ (Hint: Fermat's theorem)

#2: You can use the fact that if $\displaystyle a \equiv b \ (\text{mod }p)$ and $\displaystyle c \equiv d \ (\text{mod }p)$ then $\displaystyle ac \equiv bd \ (\text{mod } p)$. Then it's just a matter of considering $\displaystyle c = a$ and $\displaystyle d = b$

trying to use fermats theorem but still cant prove it

4. Originally Posted by bigb
a) If a^p = b^p mod p, prove that a = b mod p
Do what o_O did.
Fermat's little theorem says $\displaystyle a^p \equiv a$ and $\displaystyle b^p \equiv b$.
Therefore we can replace $\displaystyle a^p$ by $\displaystyle a$ and $\displaystyle b^p$ by $\displaystyle b$ since they are congruent.
This leaves us with $\displaystyle a\equiv b$.

5. Originally Posted by ThePerfectHacker
Do what o_O did.
Fermat's little theorem says $\displaystyle a^p \equiv a$ and $\displaystyle b^p \equiv b$.
Therefore we can replace $\displaystyle a^p$ by $\displaystyle a$ and $\displaystyle b^p$ by $\displaystyle b$ since they are congruent.
This leaves us with $\displaystyle a\equiv b$.
Can anyone work this out.. really cant seem to solve this

6. Fermat's theorem: $\displaystyle {\color{red}a^{p-1} \equiv 1 \ (\text{mod } p)}$

$\displaystyle b \equiv b^{p} \equiv a^{p} \equiv a{\color{red}a^{p - 1}} \equiv a{\color{red}(1)} \ (\text{mod } p)$

7. Originally Posted by bigb
a) If a^p = b^p mod p, prove that a = b mod p

b) If a a = b mod p, prove that a^p = b^p mod p
I made a mistake in typing out the problem for part b if that makes a differnece...it should be a^p = b^p mod p, prove that a^P = b^p mod p^2