WordGPT

The remainder of 3¹⁰⁰ divided by 7 (Fermat's little theorem)

Exercise · Level 3 (Medium)

What is the remainder when 31003^{100} is divided by 7?

3100 mod 73^{100}\bmod7

wordgptpro.com

Solution

  1. Since 7 is prime and does not divide 3, Fermat's little theorem gives 36≡1(mod7)3^{6}\equiv1\pmod7. Check: 36=729=104⋅7+13^6=729=104\cdot7+1.

  2. Divide the exponent by 6: 100=6⋅16+4100=6\cdot16+4. So

    3100=(36)16⋅34≡1⋅81≡4(mod7)3^{100}=(3^6)^{16}\cdot3^4\equiv1\cdot81\equiv4\pmod 7
    (1)
Answer44

wordgptpro.com

Need a hint?

Fermat: for a prime p not dividing a, ap−1a^{p−1} leaves remainder 1.

31003^{100} leaves remainder 4 when divided by 7.

How to work it out

  1. Since 7 is prime and does not divide 3, Fermat's little theorem gives 36≡1(mod7)3^{6}\equiv1\pmod7. Check: 36=729=104⋅7+13^6=729=104\cdot7+1.

  2. Divide the exponent by 6: 100=6⋅16+4100=6\cdot16+4. So

    3100=(36)16⋅34≡1⋅81≡4(mod7)3^{100}=(3^6)^{16}\cdot3^4\equiv1\cdot81\equiv4\pmod 7
    (1)
LaTeX source of the formulas on this page
\[ 4 \]
\[ 3^{100}=(3^6)^{16}\cdot3^4\equiv1\cdot81\equiv4\pmod 7 \]

Questions

What is the answer to: The remainder of 3¹⁰⁰ divided by 7 (Fermat's little theorem)?

31003^{100} leaves remainder 4 when divided by 7.

What is the key idea?

Fermat's little theorem lets you reduce the exponent modulo p − 1.

Is there a hint?

Fermat: for a prime p not dividing a, ap−1a^{p−1} leaves remainder 1.

Related problems

More number theory problems

    The remainder of 3¹⁰⁰ divided by 7 (Fermat's little theorem): answer and solution | WordGPT