Reaminder Problem 2

By Fermat's Little Theorem , we know that $3^{16} \equiv 1 \pmod{17}$ .

Now $247 = 15*16 + 7$ , so we now can say that

$3^{247} = 3^{(15 *16 + 7)} \equiv 3^{7} \pmod{17}$ .

Finally, $3^{7} = 2187 = 128 * 17 + 11$ , so the desired remainder is $\boxed{11}$ .

This solution might seem slow, and I guess it is, however it is very simple and do not require an extensive knowledge of theorems, etc.

Take the base, in this case 3 and put it to the power of first 1, then 2, 3 and so on, until it repeats itself. So you get:

1. 3^1 mod 17 ≡ 3

2. 3^2 mod 17 ≡ 9

3. 3^3 mod 17 ≡ 10

The first 3 seem easy, but it gets harder to do it as the exponent grows. The trick is to multiply the right hand side of the congruent sign by the base, in this case 3 and take the modulus 17 of the number to get the next step.

1. 3^4 mod 17 ≡ 10*3 mod 17 ≡ 13

2. 3^5 mod 17 ≡ 13*3 mod 17 ≡ 5

3. 3^6 mod 17 ≡ 5*3 mod 17 ≡ 15

4. 3^7 mod 17 ≡ 11

5. 3^8 mod 17 ≡ 16

6. 3^9 mod 17 ≡ 14

7. 3^10 mod 17 ≡ 8

8. 3^11 mod 17 ≡ 7

9. 3^12 mod 17 ≡ 4

10. 3^13 mod 17 ≡ 12

11. 3^14 mod 17 ≡ 2

12. 3^15 mod 17 ≡ 6

13. 3^16 mod 17 ≡ 1

14. 3^17 mod 17 ≡ 3. Notice that this the same as in step 1. So the value repeats itself every 16. exponent. So we know, that 3^247 mod 17 ≡ 3^(247 mod 16) mod 17 ≡ 3^7 mod 17. We know this is equal to step 7, and thus 3^7 mod 17 ≡ 11.

Euler's rule: 17 and 3 are co-primes, so the rule is applicable.. Euler's number of 17 = 16. Remainder(3 / 17) = 3 Rem (247/16) = 7 so Rem(3^247 / 17) => Rem(3^7 / 17) = Rem(2187 / 17) (manual)= 11.

By Fermat's Little Theorem
, 3^16 == 1(mod17).
Since 247 = (15 16) + 7, 3^247 = 3^((15 16)+7) == 3^7(mod 17).
3 to the seventh power = 2187 = 128*17 + 11,
and therefore the remainder of the original quotient is 11.

just make cycle of (3/17) remainder=3 ;(3^2/17) rem =9 ;3^3/17) rem=10 ;3^4/17)rem=13 ;3^5/17)rem=5 ;3^6/17)rem=15 ;3^7/17)rem=11 ;3^8/17)rem=-1 since we got -1 at 8th iteration implies complete cycle is of 16 now divide 247/16 remainder 7 implies 7th term So final answer 11(our 7th term in cycle)

((3^16)^15) 3^7 / 17 = 3^7/17= rem. 11 ( 3^16/17= rem 1)

Notice that $247=13*19\\$ Hence: $3^{247} = (3^{19})^{13}\\$ $(3^{19})^{13} = (3^{3} * 3^{16})^{13}\\$ By Fermat's little theorem, $3^{16} \equiv 1 \mod{17}$ hence $(3^{19})^{13} \equiv (3^{3}*1)^{13} \mod {17} \\$ $(3^{3})^{13} \equiv (27)^{13} \mod {17} \equiv (10)^{13} \mod{17}\\$ $(10)^{13} \equiv \frac{(10)^{16}}{(10)^3} \mod{17} \\$ Again, by Fermat's little theorem, $\frac{(10)^{16}}{(10)^3} \equiv \frac{1}{1000} \mod{17} \equiv \frac{1}{14} \mod{17} \equiv 14^{-1} \mod{17}\\$ By whatever method you prefer to obtain a modular inverse, $14^{-1} \equiv 11 \mod{17} \\$ Hence $3^{247} \equiv \boxed{11} \mod{17}$