Remainders Concepts

1. Basic Remainder of Powers

• Formula: If

$$a\equiv r\pmod m$$

then

$$a^n\equiv r^n\pmod m$$

Reduce the base first whenever possible.

• Example: Find the remainder when (17^5) is divided by 4. Solution:

$$17\equiv1\pmod4$$

Therefore:

$$17^5\equiv1^5\equiv\boxed{1\pmod4}$$

---

2. Cyclicity of Powers

• Formula: Powers of a number modulo (m) often repeat in a cycle. If the cycle length is (k), reduce the exponent modulo (k).

$$a^n\equiv a^{,n\bmod k}\pmod m$$

If the remainder is 0, use the (k)-th term.

• Example: Find the remainder when (7^{103}) is divided by 10. Solution: Units digits of powers of 7:

$$7,\ 9,\ 3,\ 1$$

Cycle length (=4).

$$103\div4=25\text{ remainder }3$$

So use the 3rd term:

$$\boxed{3}$$

---

3. Special Cyclicity — Powers Ending in 0, 1, 5, 6

• Formula:

$$0^n\to0,\quad1^n\to1,\quad5^n\to5,\quad6^n\to6$$

for positive integers (n).

• Example: Find the unit digit of (6^{2026}). Solution: Every positive power of 6 ends in 6:

$$6^{2026}\equiv\boxed{6\pmod{10}}$$

---

4. Euler’s Totient Theorem

• Formula: If

$$\gcd(a,n)=1$$

then:

$$a^{\phi(n)}\equiv1\pmod n$$

where

$$\phi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$$

• Example: Find the remainder when (3^{100}) is divided by 7. Solution: Since 7 is prime:

$$\phi(7)=6$$ $$3^6\equiv1\pmod7$$

Now:

$$100=6(16)+4$$

Therefore:

$$3^{100}\equiv3^4=81\equiv\boxed{4\pmod7}$$

---

5. Fermat’s Little Theorem

• Formula: If (p) is prime and (p\nmid a):

$$a^{p-1}\equiv1\pmod p$$

Equivalently:

$$a^p\equiv a\pmod p$$

• Example: Find the remainder when (2^{100}) is divided by 7. Solution:

$$2^6\equiv1\pmod7$$

Since:

$$100=6(16)+4$$ $$2^{100}\equiv2^4=16\equiv\boxed{2\pmod7}$$

---

6. Binomial Theorem — Divisor ± 1 Method

• Formula: Write the base as:

$$a=km\pm1$$

Then:

$$(km\pm1)^n\equiv(\pm1)^n\pmod m$$

because all other binomial terms contain (m).

• Example: Find the remainder when (2^{10}) is divided by 3. Solution:

$$2=3-1$$

Hence:

$$2^{10}=(3-1)^{10}$$

All terms except the final ((-1)^{10}) are divisible by 3.

$$2^{10}\equiv1\pmod3$$ $$\boxed{1}$$

---

7. Binomial Expansion — General Remainder

• Formula:

$$(a+b)^n =\sum_{k=0}^n{n\choose k}a^{n-k}b^k$$

Choose (a) as a multiple of the divisor so that most terms vanish modulo the divisor.

• Example: Find the remainder when (10^{5}+3^{5}) is divided by 7. Solution:

$$10\equiv3\pmod7$$

Therefore:

$$10^5+3^5\equiv3^5+3^5$$ $$=2(243)=486$$ $$486\equiv\boxed{3\pmod7}$$

---

8. Remainder of Negative Powers/Base

• Formula: If

$$a\equiv-r\pmod m$$

then:

$$a^n\equiv(-r)^n\pmod m$$

Thus the sign depends on whether (n) is even or odd.

• Example: Find the remainder when (8^{15}) is divided by 9. Solution:

$$8\equiv-1\pmod9$$

Therefore:

$$8^{15}\equiv(-1)^{15}=-1\equiv\boxed{8\pmod9}$$

---

9. Finding (\phi(n)) for Composite Modulus

• Formula: If

$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$

then:

$$\phi(n)=n\left(1-\frac1{p_1}\right) \left(1-\frac1{p_2}\right)\cdots \left(1-\frac1{p_k}\right)$$

• Example: Find (\phi(20)). Solution:

$$20=2^2\times5$$ $$\phi(20)=20\left(1-\frac12\right) \left(1-\frac15\right)$$ $$=20\times\frac12\times\frac45 =\boxed{8}$$

---

10. Remainder of a Large Power with Composite Modulus

• Formula: If (\gcd(a,n)=1):

$$a^{\phi(n)}\equiv1\pmod n$$

Reduce the exponent modulo (\phi(n)).

• Example: Find the remainder when (3^{100}) is divided by 20. Solution:

$$\phi(20)=8$$

Since (\gcd(3,20)=1):

$$3^8\equiv1\pmod{20}$$ $$100=8(12)+4$$

Thus:

$$3^{100}\equiv3^4=81\equiv\boxed{1\pmod{20}}$$

---

11. Modular Inverse

• Formula: The modular inverse of (a) modulo (m) is (a^{-1}) such that:

$$aa^{-1}\equiv1\pmod m$$

It exists when:

$$\gcd(a,m)=1$$

• Example: Find the inverse of 3 modulo 7. Solution: We need:

$$3x\equiv1\pmod7$$

Since:

$$3\times5=15\equiv1\pmod7$$

Therefore:

$$\boxed{3^{-1}\equiv5\pmod7}$$

---

12. Chinese Remainder Theorem — Two Congruences

• Formula: For

$$x\equiv a\pmod m,\qquad x\equiv b\pmod n$$

where (\gcd(m,n)=1), there is a unique solution modulo (mn).

• Example: Find the smallest positive (x) such that

$$x\equiv2\pmod3,\qquad x\equiv3\pmod5.$$

Solution: Numbers congruent to 2 modulo 3:

$$2,5,8,11,\ldots$$

Among these:

$$8\equiv3\pmod5$$

Therefore:

$$\boxed{x=8}$$

---

13. Chinese Remainder Theorem — Three Congruences

• Formula: For pairwise coprime (m_1,m_2,m_3):

$$x\equiv a_i\pmod{m_i}$$

Solve two congruences first, then combine the result with the third.

• Example: Find the smallest positive (x) satisfying

$$x\equiv1\pmod2,\quad x\equiv2\pmod3,\quad x\equiv3\pmod5.$$

Solution: Numbers satisfying (x\equiv3\pmod5):

$$3,8,13,18,23,\ldots$$

Check modulo 3:

$$8\equiv2\pmod3$$

Also:

$$8\equiv0\pmod2$$

not suitable. Next:

$$23\equiv2\pmod3,\qquad23\equiv1\pmod2$$

Therefore:

$$\boxed{x=23}$$

---

14. Wilson’s Theorem

• Formula: For a prime (p):

$$(p-1)!\equiv-1\pmod p$$

• Example: Find the remainder when (6!) is divided by 7. Solution: Since 7 is prime:

$$6!\equiv-1\pmod7$$ $$-1\equiv\boxed{6\pmod7}$$

---

15. Factorial Remainders Using Wilson’s Theorem

• Formula: For prime (p):

$$(p-1)!\equiv-1\pmod p$$

and:

$$(p-k)! \text{ can often be related to } (p-1)!$$

by cancelling factors modulo (p).

• Example: Find the remainder when (8!) is divided by 11. Solution:

$$10!=10\times9\times8!$$

By Wilson:

$$10!\equiv-1\pmod{11}$$

Since:

$$10\times9=90\equiv2\pmod{11}$$

Thus:

$$2(8!)\equiv-1\equiv10\pmod{11}$$

The inverse of 2 modulo 11 is 6:

$$8!\equiv10\times6=60\equiv\boxed5\pmod{11}$$

---

Advanced Variants

16. Chinese Remainder Theorem — General Construction

• Formula: For

$$x\equiv a_i\pmod{m_i},$$

let

$$M=m_1m_2\cdots m_k,\qquad M_i=\frac{M}{m_i}$$

and let (y_i) satisfy:

$$M_iy_i\equiv1\pmod{m_i}.$$

Then:

$$x\equiv\sum a_iM_iy_i\pmod M.$$

• Example: Find the smallest (x) satisfying

$$x\equiv2\pmod3,\qquad x\equiv3\pmod5.$$

Solution:

$$M=15,\quad M_1=5,\quad M_2=3$$

Inverses:

$$5(2)\equiv1\pmod3$$ $$3(2)\equiv1\pmod5$$

Therefore:

$$x=2(5)(2)+3(3)(2)=38$$ $$38\equiv\boxed8\pmod{15}$$

Smallest positive solution:

\boxed8}

---

17. Non-Coprime Modular Equations

• Formula: The system

$$x\equiv a\pmod m,\qquad x\equiv b\pmod n$$

has a solution only if:

$$a\equiv b\pmod{\gcd(m,n)}.$$

• Example: Find the smallest positive (x) satisfying

$$x\equiv1\pmod4,\qquad x\equiv5\pmod6.$$

Solution:

$$\gcd(4,6)=2$$

and:

$$1\equiv5\pmod2$$

so a solution exists.

Numbers (1\pmod4):

$$1,5,9,13,\ldots$$ $$5\equiv5\pmod6$$

Therefore:

$$\boxed{x=5}$$

---

18. Large Exponents with Multiple Modular Reductions

• Formula: Reduce the exponent using the smallest convenient cycle/order, or use:

$$a^{\phi(n)}\equiv1\pmod n$$

when (\gcd(a,n)=1).

• Example: Find the remainder when (2^{1000}) is divided by 13. Solution:

$$2^{12}\equiv1\pmod{13}$$

Since:

$$1000=12(83)+4$$ $$2^{1000}\equiv2^4=16\equiv\boxed3\pmod{13}$$

---

19. Remainder of a Sum/Difference of Large Powers

• Formula: If

$$a\equiv r\pmod m,\qquad b\equiv s\pmod m,$$

then:

$$a^n\pm b^n\equiv r^n\pm s^n\pmod m.$$

• Example: Find the remainder when (5^{20}+7^{20}) is divided by 6. Solution:

$$5\equiv-1\pmod6,\qquad7\equiv1\pmod6$$

Therefore:

$$5^{20}+7^{20} \equiv(-1)^{20}+1^{20}$$ $$=1+1 =\boxed2\pmod6$$

---

20. Remainder of Polynomial Expressions

• Formula: If

$$a\equiv r\pmod m,$$

replace (a) by (r) throughout any polynomial in (a).

• Example: Find the remainder when

$$3^{10}+2(3^5)+7$$

is divided by 5. Solution:

$$3^4\equiv1\pmod5$$

Thus:

$$3^{10}\equiv3^2=9\equiv4$$

and:

$$3^5\equiv3$$

Therefore:

$$4+2(3)+7=17$$ $$17\equiv\boxed2\pmod5$$