The minimum positive integer p such that 3p ≡ 1 (mod 17) is:

Concept

For integers a and b and a positive integer n, a ≡ b (mod n) means that a and b leave the same remainder when divided by n. Thus 3p ≡ 1 (mod 17) asks when the remainder of 3p upon division by 17 is 1.

The multiplicative order of a modulo n is the least positive exponent k for which ak ≡ 1 (mod n). When n is prime and gcd(a, n) = 1, Fermat’s Little Theorem implies that this order divides n − 1.

Application

Here a = 3 and n = 17, so the order must divide 16. Its only possible values are 1, 2, 4, 8, and 16.

1. Compute the first powers: 31 ≡ 3 and 32 ≡ 9 (mod 17).

2. Square the previous residue: 34 ≡ 92 = 81 ≡ 13 (mod 17).

3. Square again: 38 ≡ 132 = 169 ≡ 16 ≡ −1 (mod 17).

4. Therefore none of the possible smaller orders 1, 2, 4, or 8 gives residue 1.

5. Squaring 38 ≡ −1 gives 316 ≡ (−1)2 ≡ 1 (mod 17). Hence the least exponent is p = 16.

Cross-check

Fermat’s Little Theorem independently guarantees 316 ≡ 1 (mod 17). Since every smaller possible order must divide 16 and the divisors 1, 2, 4, and 8 have all been eliminated, 16 is minimal.