The minimum positive integer p such that 3^p (mod 17) = 1 is A. 5 B. 8 C. 12 D. 16

GATE 2007 · Discrete Mathematics · Number Theory · medium

Answer: The minimum positive integer p such that 3^p ≡ 1 (mod 17) is 16 (option D).

1. Bound the order using Fermat's Little Theorem: With a = 3, p = 17: 3^16 ≡ 1 (mod 17). The order of 3 mod 17 must divide 16. Divisors of 16 are 1, 2, 4, 8, 16.
2. Check smaller divisors of 16: 3^1 = 3 (mod 17) != 1. 3^2 = 9 (mod 17) != 1. 3^4 = 81 = 4*17 + 13, so 3^4 ≡ 13 (mod 17) != 1. 3^8 ≡ 13^2 = 169 = 9*17 + 16, so 3^8 ≡ 16 ≡ -1 (mod 17) != 1. None of 1, 2, 4, 8 works. Therefore the order is 16, giving p = 16 (option D).