# Thread: Help With Congruence Problems

1. ## Help With Congruence Problems

Hello, everyone! Just wanted some ideas regarding the following problems.

1) Let a and b be integers and p be a prime number. Prove the following:
a) a^2 = b^2 mod p implies that a = ħb mod p.
b) a^2 = a mod p implies that a = 0 mod p or a = 1 mod p.

2) Let p be prime and (a,p) = (b,p) = 1. Prove the following:
a) a^p = b^p mod p implies that a = b mod p.
b) a^p = b^p mod p implies that a^p = b^p mod p^2.

Thanks!

2. Originally Posted by carabidus
Hello, everyone! Just wanted some ideas regarding the following problems.

1) Let a and b be integers and p be a prime number. Prove the following:
a) a^2 = b^2 mod p implies that a = ħb mod p.

$\color{red}a^2 \equiv b^2\,(mod\,p)\Longleftrightarrow (a-b)(a+b)=a^2-b^2\equiv 0\,(mod\,p)\Longleftrightarrow p\mid(a-b)(a+b)$
$\color{red}\mbox{Since p is a prime then....}$

b) a^2 = a mod p implies that a = 0 mod p or a = 1 mod p.

$\color{red}a^2=a\Longleftrightarrow a(a-1)=0$

2) Let p be prime and (a,p) = (b,p) = 1. Prove the following:
a) a^p = b^p mod p implies that a = b mod p.

$\color{red}\mbox{Read about Fermat's Little Theorem (FLT):}a^p\equiv a (mod\,p)$

b) a^p = b^p mod p implies that a^p = b^p mod p^2.

$\color{red}\mbox{Apply FLT to get}\,\,a \equiv b\,(mod\,p)\Longrightarrow a-b=kp\,,\,\,with\,\,k\in \mathbb{Z}\,...etc.$

$\color{red}Tonio$

Thanks!
.

3. Hey, thanks Tonio! Here are more congruent problems I've been pondering:

1) Show that for every positive integer m there are infinitely many Fibonacci numbers F_n such that m divides F_n .

2) Let p be an odd prime and k be a positive integer. Show that x^2=1 mod p^k has exactly 2 two noncongruent solutions.

3) Develop a test for divisibility based on the fact that 10^3=1 mod 37. Use this to check 11092785 for divisibility by 37.

4) Let p be prime and let {a_1, a_2, ... , a_p} and {b_1, b_2, ... , b_p} be complete sets of residues mod p. Show that {a_1*b_1, a_2*b_2 , ... , a_p*b_p} is NOT a complete set of residues mod p.

Thank you!