number theory - modulo?
Prove: Let a and n be natural numbers with (a, n) = 1. then gcd (a^j, n) = 1 for any natural number j.
- 9 years agoFavorite Answer
Let gcd(a, n) = 1. Assume by contradiction that gcd(a^j, n) = d > 1. Then, d | a^j and d | n. By the Prime Factorization Theorem, since d > 1 there exists a prime p such that p divides d. Since p | d and d | a^j and d | n, then we see that p | a^j and p | n. Since p | a^j we see that p | a. Now since p | a and p | n we see that p | gcd(a, n). But gcd(a, n) = 1 so this would mean that p | 1. So p <= 1, but this is a contradiction since p is prime and primes are greater than one. Thus, the assume that gcd(a^j, n) > 1 is false. Therefore, gcd(a^j, n) = 1.
- PaulaLv 79 years ago
(a, n) = 1
means a and n share no prime factors. i.e. any prime which is a factor a is not a factor of n, and vice versa.
And a^j has the same prime factors as a...