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.

2 Answers

  • Favorite 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.

  • Paula
    Lv 7
    9 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...

Still have questions? Get your answers by asking now.