Question

Show that if (p) is a prime, (a) is an integer, and (k) is a nonnegative integer, then (a^(1 - k(p-1)) equiv a pmodp).

a) (a^(1 - k) equiv a pmodp)
b) (a^(k(p-1) - 1) equiv a pmodp)
c) (a^(k(p-1) + 1) equiv a pmodp)
d) (a^(1 + k(p-1)) equiv a pmodp)

Answer 1

Fermat's Little Theorem states that a^(p-1) ≡ 1 (mod p) for a prime p and an integer a not divisible by p. Raising both sides to the power of k and then multiplying by a, we derive that a^(1 + k(p-1)) ≡ a (mod p), demonstrating that option (d) is correct.

Step-by-step explanation:

According to Fermat's Little Theorem, if p is a prime number and a is an integer not divisible by p, then ap-1 ≡ 1 (mod p). Let's use this theorem to show that for any integer a and nonnegative integer k, the expression a1 - k(p-1) ≡ a (mod p).

First, we raise both sides of Fermat's Little Theorem to the power of k: (ap-1)k ≡ 1k (mod p) which simplifies to ak(p-1) ≡ 1 (mod p). Now, we multiply both sides by a to get a × ak(p-1) ≡ a × 1 (mod p) which simplifies to a1 + k(p-1) ≡ a (mod p).

Thus, option (d) is correct and it shows that a1 + k(p-1) ≡ a (mod p). Note that this holds for any integer a, including when a is divisible by p, since in that case both sides are equivalent to 0 modulo p.