bigp0ppa1046
New member
- Joined
- Jan 30, 2007
- Messages
- 18
Our method for solving x^k=b (mod m) is to first find integers u and v satisfying ku-Φ(m)v=1, and then the solution is x=b^u (mod m). However, we only showed that this works provided that gcd(b,m)=1, since we used Euler's formula b^ Φ(m)=1 (mod m).
a)If m is a product of distinct primes, show that x=b^u (mod m) is always a solution to x^k=b (mod m), even if gcd(b,m)>1.
b) Show that our method does not work for the congruence x^5= 6 (mod 9).
= sign means "congruent to"
a)If m is a product of distinct primes, show that x=b^u (mod m) is always a solution to x^k=b (mod m), even if gcd(b,m)>1.
b) Show that our method does not work for the congruence x^5= 6 (mod 9).
= sign means "congruent to"