Hi, I'm new here, so please forgive me if I'm using incorrect symbols.
I've been working on this problem for a while, but I can't seem to understand it.
We've been solving to find the kth root modulo m where we find u and v for ku - phi(m)v = 1. This problem states that we've so far been solving when x is congruent to b^u(mod m) provided that gcd(b,m) = 1, since Euler's formula would give us
b^phi(m) is congruent to 1 (mod m). What I need to prove is this:
If m is a product of distinct primes, show that x congruent to b^u(mod m) is always a solution to x^k congruent to b (mod m), even if gcd(b,m)>1.
I was wondering if someone could give me some helpful hints on how to start this problem. So far all I've done is write m as a product of distinct primes.
I've been working on this problem for a while, but I can't seem to understand it.
We've been solving to find the kth root modulo m where we find u and v for ku - phi(m)v = 1. This problem states that we've so far been solving when x is congruent to b^u(mod m) provided that gcd(b,m) = 1, since Euler's formula would give us
b^phi(m) is congruent to 1 (mod m). What I need to prove is this:
If m is a product of distinct primes, show that x congruent to b^u(mod m) is always a solution to x^k congruent to b (mod m), even if gcd(b,m)>1.
I was wondering if someone could give me some helpful hints on how to start this problem. So far all I've done is write m as a product of distinct primes.