Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Prime Number Proof Question?

Let M be the product of two distinct prime numbers p1 and p2, and let a be an integer chosen so that the greatest common factor of a and M is 1.

By considering the value of a^(p1-1)(p2-1) modulo p1 and modulo p2, or otherwise, prove that a^(p1-1)(p2-1) ≡ 1 mod M.

1 Answer

Relevance
  • 8 years ago
    Favorite Answer

    By Fermat's little theorem, a^(p1-1) ≡ 1 mod p1.

    So a^(p1-1)(p2-1) = [a^(p1-1)]^(p2-1) ≡ 1 mod p1.

    Likewise, a^(p2-1) ≡ 1 mod p2, and

    so a^(p1-1)(p2-1) = [a^(p2-1)]^(p1-1) ≡ 1 mod p2 as well.

    But then a^(p1-1)(p2-1) - 1 is divisible by both p1 and p2;

    so it must be divisible by their product M, QED

Still have questions? Get your answers by asking now.