Anonymous
Anonymous asked in Science & MathematicsMathematics · 2 months ago

How do I show that a^(p-2) mod(p-1) = a^(-1) mod(p-1), where p is a prime number?

Hello.

Could someone please help me figure out how I can show that a^(p-2) mod(p-1) = a^(-1) mod(p-1), where p is a prime number?

If it were (p-2) mod(p-1) = -1 mod(p-1), it would make sense to me because (p-2)-(p-1)=-1, but it involves exponents, so I guess the way to understand it is via some other technique.

Any input would be GREATLY appreciated!

2 Answers

Relevance
  • ?
    Lv 7
    2 months ago

    the claim 

    a^(p-2) mod(p-1) ≡  a^(-1) mod(p-1)

    where p is a prime

    it makes no sense unless p > 2

    for the modular inverse to exist, a must be relatively prime to (p-1). 

    it is trivially true for a ≡ 1

    multiplying both sides by a gives

    a^(p-1) mod(p-1) ≡ 1 mod(p-1)

    which would be true by Fermat’s little theorem if the modulus was a prime p

    p-1 is not prime, hence we need Euler’s theorem

    a^Φ(n) ≡ 1 mod(n)

    however Φ(n) does not equal n-1 unless n is a prime

    so looking at cases:

    p = 5

    3^2 ≡ 1 mod(4)

    3^3 ≡ 3 ≡ 3^(-1) mod(4)

    p = 7

    5^2 ≡ 1 mod(6)

    5^5 ≡ 5 ≡ 5^(-1) mod(6)

    p = 11

    3*7 ≡ 1 mod(10)

    3^9 ≡ 3 not ≡ 7 ≡ 3^(-1) mod(10)

    thus the proposition is false

  • 2 months ago

    First examine an example.  Let's say p = 7.  Then the equation says

    a^5 mod(6) = a^(-1) mod(6), or

    a^6 mod(6) = a^0 mod(6) = 1 mod(6).

    This is obviously not true if "a" and 6 have a common divisor.

Still have questions? Get answers by asking now.