Modular arithmetic — definition, addition, multiplication, congruence

2.5.6 · Maths › Number Theory (Intermediate)

Overview

Modular arithmetic ek aisi arithmetic hai jo ek certain value tak pahunchne ke baad "wrap around" karti hai — us value ko modulus kehte hain. Yeh clock arithmetic, cyclic patterns, cryptography, aur computer science hash functions ki mathematical foundation hai.

Core Concepts

Numbers ko infinite extend karne ki jagah, hum unhe unke remainder ke basis pe equivalence classes mein partition karte hain — jab unhe ek fixed number (modulus) se divide kiya jaata hai. Isse hum:

• Bade numbers ke calculations simplify kar sakte hain (cryptography mein yahi hota hai!)
• Divisibility mein patterns dhundh sakte hain
• Cyclic structures ke saath kaam kar sakte hain (week ke din, mahine, rotations)

Key insight: Modular arithmetic mein do numbers "same" hote hain agar woh modulus se divide karne par same remainder dete hain.

Equivalent definition: $a\equiv b(\mathrm{mod}n)$ agar aur sirf agar $a$ aur $b$, $n$ se divide karne par same remainder dete hain.

Iska matlab kya hai? $a$ aur $b$ ka difference $n$ ka ek multiple hai. Jab hum integers ko remainder ke basis pe groups mein divide karte hain, toh woh dono same "bucket" mein hote hain.

First Principles se:

1. Addition: Agar $a\equiv b(\mathrm{mod}n)$ aur $c\equiv d(\mathrm{mod}n)$, toh: $a+c\equiv b+d(\mathrm{mod}n)$

Kyun?

• Hum jaante hain $a-b=k_{1}n$ aur $c-d=k_{2}n$ kisi integers $k_1,k_2$ ke liye
• Inhe add karo: $(a-b)+(c-d)=k_{1}n+k_{2}n$
• Rearrange karo: $(a+c)-(b+d)=(k_1+k_2)n$
• Kyunki $k_1+k_2$ ek integer hai, $(a+c)\equiv (b+d)(\mathrm{mod}n)$

2. Multiplication: Agar $a\equiv b(\mathrm{mod}n)$ aur $c\equiv d(\mathrm{mod}n)$, toh: $ac\equiv bd(\mathrm{mod}n)$

Kyun?

• Hamare paas hai $a=b+k_{1}n$ aur $c=d+k_{2}n$
• Multiply karo: $ac=(b+k_{1}n)(d+k_{2}n)$
• Expand karo: $ac=bd+b{k}_{2}n+d{k}_{1}n+k_1{k}_2{n}^2$
• Factor karo: $ac=bd+n(b{k}_2+d{k}_1+k_1{k}_{2}n)$
• Therefore: $ac-bd=n\cdot (\text{integer})$, toh $ac\equiv bd(\mathrm{mod}n)$

3. Power Rule: Agar $a\equiv b(\mathrm{mod}n)$, toh: $a^k\equiv b^k(\mathrm{mod}n)$

Kyun? Multiplication rule ko $k$ baar repeatedly apply karo.

Solution:

• Method 1 (Difference): $23-8=15=3\times 5$. Kyunki difference 5 ka multiple hai, haan.
• Method 2 (Remainder): $23=4\times 5+3$ (remainder 3), $8=1\times 5+3$ (remainder 3). Same remainder, haan.

Yeh kyun important hai: Dono numbers mod 5 mein "remainder 3" equivalence class mein hain.

Solution:

• Step 1: Pehle har number ko reduce karo

  • $17=2\times 7+3$, toh $17\equiv 3(\mathrm{mod}7)$
  • $23=3\times 7+2$, toh $23\equiv 2(\mathrm{mod}7)$
  • Yeh step kyun? Chhote numbers ke saath kaam karna aasaan hai, aur hum operate karne se pehle reduce kar sakte hain.

• Step 2: Reduced numbers ko add karo

  • $3+2=5$
  • Yeh step kyun? Addition rule se, $(17+23)\equiv (3+2)(\mathrm{mod}7)$

• Step 3: Result

  • $5<7$, toh $5$ already standard form mein hai
  • Yeh step kyun? Hum answer ko $[0,n-1]$ range mein chahte hain.

Answer: $(17+23)\equiv 5(\mathrm{mod}7)$

Verification: $17+23=40=5\times 7+5$. Remainder 5 hai. ✓

Solution:

• Step 1: Har factor ko reduce karo

  • $13=2\times 5+3$, toh $13\equiv 3(\mathrm{mod}5)$
  • $8=1\times 5+3$, toh $8\equiv 3(\mathrm{mod}5)$
  • Yeh step kyun? Chhote numbers ke saath kaam karne se overflow nahi hota aur calculation simplify ho jaati hai.

• Step 2: Reduced numbers ko multiply karo

  • $3\times 3=9$
  • Yeh step kyun? Multiplication rule se, $(13\times 8)\equiv (3\times 3)(\mathrm{mod}5)$

• Step 3: Result ko reduce karo

  • $9=1\times 5+4$, toh $9\equiv 4(\mathrm{mod}5)$
  • Yeh step kyun? Final answer standard form $[0,4]$ mein hona chahiye.

Answer: $(13\times 8)\equiv 4(\mathrm{mod}5)$

Verification: $13\times 8=104=20\times 5+4$. Remainder 4 hai. ✓

Solution:

• Step 1: Base ko reduce karo

  • $7=1\times 6+1$, toh $7\equiv 1(\mathrm{mod}6)$
  • Yeh step kyun? Agar base kisi simple cheez mein reduce ho jaaye, toh power trivial ban jaati hai.

• Step 2: Power rule apply karo

  • $7^{100}\equiv 1^{100}(\mathrm{mod}6)$
  • Yeh step kyun? Power rule se, congruence exponentiation ke under preserved rehti hai.

• Step 3: Evaluate karo

  • $1^{100}=1$
  • Yeh step kyun? 1 ki koi bhi power 1 hoti hai.

Answer: $7^{100}\equiv 1(\mathrm{mod}6)$

Key insight: Base ko pehle reduce karna impossible-lagti calculations ko trivial bana sakta hai!

Kyun sahi lagta hai: Yeh actually kaam karta hai! Lekin bade numbers ke liye (jaise $1234567+9876543(\mathrm{mod}7)$), pehle poora sum calculate karna overflow ya unnecessary complexity cause kar sakta hai.

Fix: Pehle har operand ko reduce karo, phir operate karo. Yeh addition/multiplication rules ke zariye hamesha valid hai, aur zyada efficient hai.

Steel-man: "Calculate then reduce" approach mathematically correct hai, bas computationally inefficient hai. Modular arithmetic rules isliye exist karte hain taaki hum calculation ke dauran reduce kar sakein.

Kyun sahi lagta hai: Regular arithmetic mein hum dono sides ko same number se divide kar sakte hain.

Fix: Modular arithmetic mein division hamesha defined nahi hoti. Tum sirf $a$ se tabhi divide kar sakte ho jab $\gcd (a,n)=1$ ho (yaani $a$ aur $n$ coprime hain). Yahan $\gcd (6,15)=3\ne 1$, toh hum 6 se divide nahi kar sakte.

Sahi approach:

• Notice karo ki $\gcd (6,15)=3$, jo 6 aur 9 dono ko divide karta hai
• Simplify karo: $6x\equiv 9(\mathrm{mod}15)$ ban jaata hai $2x\equiv 3(\mathrm{mod}5)$
• Ab solve kar sakte hain: dono sides ko 2 ke modular inverse se multiply karo mod 5

Steel-man: Regular algebra ka intuition powerful hai, lekin modular arithmetic ke rules alag hain. Division valid hai ya nahi, yeh check karne ke liye hamesha gcd check karo.

Kyun sahi lagta hai: Programming mein, kuch languages negative remainders return karti hain.

Fix: Mathematics mein, hum hamesha result $[0,n-1]$ mein chahte hain. Negative numbers ko convert karo: $-3\equiv -3+7\equiv 4(\mathrm{mod}7)$

General rule: Agar tumhe negative result $r$ mile, tab tak $n$ ke multiples add karo jab tak $[0,n-1]$ na aa jaaye: $r\equiv r+kn(\mathrm{mod}n)$ jahan $k$ aisa choose karo ki result non-negative ho.

Yahi modular arithmetic hai! "12" ko modulus kehte hain — yahi woh point hai jahan tum wrap around karte ho. Do positions "same" hain agar woh circle par same spot hain.

Jab hum $13\equiv 1(\mathrm{mod}12)$ likhte hain, hum keh rahe hain "13 aur 1 ek 12-ghante ki clock par same position hain."

Cool part yeh hai: tum is circular track par add aur multiply kar sakte ho, aur sab kuch kaam karta hai! Agar tum position 5 par ho aur ek dost position 8 par hai, toh saath mein tum $5+8=13$ steps gaye, jo position 1 hai. Agar tum track par 5 baar jaate ho, har baar 8 steps lete hue, toh tum total $5\times 8=40$ steps lete ho, jo tumhe position 4 par land karta hai (kyunki $40=3\times 12+4$).

Reminder: $a\equiv b(\mathrm{mod}n)$ ka matlab hai "$a$ aur $b$ ek $n$-ghante ki clock par same time dikhate hain."

Properties of Congruence

Congruence modulo $n$ ek equivalence relation hai, yaani:

1. Reflexive: $a\equiv a(\mathrm{mod}n)$ (har number apne aap se congruent hai)
2. Symmetric: Agar $a\equiv b(\mathrm{mod}n)$, toh $b\equiv a(\mathrm{mod}n)$
3. Transitive: Agar $a\equiv b(\mathrm{mod}n)$ aur $b\equiv c(\mathrm{mod}n)$, toh $a\equiv c(\mathrm{mod}n)$

Yeh kyun important hai: Yeh properties matlab hai ki congruence integers ko distinct equivalence classes mein partition karti hai (jinhein residue classes kehte hain). Har integer exactly ek class mein belong karta hai.

Modulus $n$ ke liye, exactly $n$ residue classes hoti hain: $[0],[1],[2],\dots ,[n-1]$.

The Residue Classes

Modulus 5 ke liye, residue classes hain:

• $[0]=\{\dots ,-10,-5,0,5,10,15,\dots \}$
• $[1]=\{\dots ,-9,-4,1,6,11,16,\dots \}$
• $[2]=\{\dots ,-8,-3,2,7,12,17,\dots \}$
• $[3]=\{\dots ,-7,-2,3,8,13,18,\dots \}$
• $[4]=\{\dots ,-6,-1,4,9,14,19,\dots \}$

Har integer exactly inhi classes mein se ek mein hai. Hum ${\mathbb{Z}}_5=\{0,1,2,3,4\}$ likhte hain residue classes mod 5 ke set ke liye.

Connections

• Division Algorithm — remainders ki foundation
• GCD and LCM — determine karta hai kab modular division possible hai
• Fermats Little Theorem — modular exponentiation use karta hai
• Eulers Theorem — modular arithmetic use karke Fermat's theorem ko generalize karta hai
• Chinese Remainder Theorem — congruences ke systems solve karta hai
• Modular Inverses — modular arithmetic mein division
• RSA Cryptography — poori tarah bade primes ke saath modular arithmetic par built hai
• Linear Congruences — $ax\equiv b(\mathrm{mod}n)$ solve karna
• Quadratic Residues — kaun se numbers mod $n$ perfect squares hain

Practice Problems

1. Verify karo ki $17\equiv 38(\mathrm{mod}7)$ dono definitions use karke
2. $(45+67)\mathrm{mod}11$ compute karo pehle reduce karke
3. $(13\times 17)\mathrm{mod}6$ efficiently find karo
4. $9^{50}\mathrm{mod}8$ calculate karo (hint: pehle base reduce karo!)
5. Prove karo ki agar $a\equiv b(\mathrm{mod}n)$, toh $a^2\equiv b^2(\mathrm{mod}n)$
6. Saare $x$ find karo jaise ki $x^2\equiv 1(\mathrm{mod}8)$

#flashcards/maths

What is the definition of congruence modulo n? :: Do integers $a$ aur $b$ congruent modulo $n$ hote hain (likha jaata hai $a\equiv b(\mathrm{mod}n)$) agar unka difference $n$ ka multiple ho, yaani $a-b=kn$ kisi integer $k$ ke liye.

State the addition rule in modular arithmetic :: Agar $a\equiv b(\mathrm{mod}n)$ aur $c\equiv d(\mathrm{mod}n)$, toh $a+c\equiv b+d(\mathrm{mod}n)$.

Why can we reduce numbers before operating in modular arithmetic? :: Kyunki addition aur multiplication rules guarantee karte hain ki $(a\mathrm{mod}n)+(b\mathrm{mod}n)\equiv (a+b)(\mathrm{mod}n)$, aur similarly multiplication ke liye bhi. Isse calculations zyada efficient ho jaati hain.

How do you handle negative numbers in modular arithmetic? :: Modulus ke multiples add karo jab tak result $[0,n-1]$ range mein na aa jaaye. For example, $-3\equiv 4(\mathrm{mod}7)$ kyunki $-3+7=4$.

What is the clock face analogy for modular arithmetic? :: Modular arithmetic ek clock ki tarah kaam karta hai: modulus value reach karne ke baad, 0 par wrap around ho jaata hai. Mod 12 ke liye, 11 ke baad 0 aata hai. Do numbers congruent hain agar woh clock par same position point karte hain.

Concept Map

Deep Dive

• D1 · Foundations — har symbol zero se
• D2 · Visual walkthrough — pictures mein derivation
• D3 · Worked examples — har scenario
• D4 · Exercises — graded, full solutions
• D5 · Question bank — concept traps