Modular Arithmetics

A clock is a basic example of modulo arithmetics.

⏰ Hours are on module 12 (or 24), while minutes and seconds are on module 60.

En este caso el minuto zero y el minuto sesenta son congruentes: la aguja apunta al mismo sitio.

Dos números son congruentes si son iguales en la operación módulo.

a mod m ≡ b mod m
aº ≡ bº 

a ≡ m mod b ⟺ ∃k∈ℤ, a-b = km

Es equivalente a la función resto. En números naturales:

a mod m = a resto m = a rem m -- Reminder
⌊a∕m⌋+ rem

El resto r

r ∈ [0,m) ⊂ ℕ

también se le llama el menor residuo (no negativo).

📌 Theorem: Modular addition

If:

x≡a(mod12)

y≡b(mod12)

Then:

x+y≡(a+b)(mod12)

📌 Proof

Since $x≡a(mod12)$, by the definition of modular congruence, we know:

• $x=a+12k$ for some integer $k$.

Similarly, since $y≡b(mod12)$, we also have:

• $y=b+12m$ for some integer $m$.

Now, add both equations:

x+y=(a+12k)+(b+12m)

x+y=(a+b)+12(k+m)

Since $12(k+m)$ is a multiple of $12$, we conclude:

x+y≡a+b(mod12)

✅ Proof Complete! 🎉

📌 Theorem (Modular Multiplication)

If:

x≡a(mod12),y≡b(mod12)

Then:

x⋅y≡a⋅b(mod12)

📌 Proof

Since $x≡a(mod12)$, by the definition of modular congruence, we write:

• $x=a+12k$ for some integer $k$.

Similarly, since $y≡b(mod12)$, we also have:

• $y=b+12m$ for some integer $m$.

Now, multiply both sides:

• $x⋅y=(a+12k)⋅(b+12m)$

Expanding using the distributive property:

• $x⋅y=a⋅b+12k⋅b+12m⋅a+12k⋅12m$

Rewriting:

• $x⋅y=a⋅b+12(kb+ma+12km)$

Since $12(kb+ma+12km)$ is a multiple of 12, it follows that:

• $x⋅y≡a⋅b(mod12)$

✅ Proof Complete! 🎉

📌 Why This Works

This is a general property of modular arithmetic, which holds for any modulus $n$:

x≡a(modn),y≡b(modn)⇒x⋅y≡a⋅b(modn)

x≡a(modn),y≡b(modn)⇒x+y≡a+b(modn).

This is fundamental in number theory, cryptography, and abstract algebra because it ensures that modular arithmetic is consistent with normal arithmetic rules.

📌 What is a Modular Inverse?

The modular inverse of a number $x_{(mod n)}$ is a number $y$ such that:

x⋅y≡1_{(modn)}

This means $y$ "undoes" the multiplication of $x$ , leaving 1! Just like how $\frac{1}{x}$​ is the inverse of $x$ ($x¨$) in regular arithmetic.

🔹 Example in mod 7:

• $3×5≡1(mod7)$ So, the modular inverse of $3_{(mod 7)}$ is $5$, because:

📌 When Does a Modular Inverse Exist?

A modular inverse only exists if $x$ and $n$ are coprime (i.e., $gcd⁡(x,n)=1$ ).

🔹 Key Theorem:

\text{
A number x has an inverse-(mod n) if and only if gcd⁡(x,n)=1.
}

• ✅ If $gcd⁡(x,n)=1$, the inverse exists.
• ❌ If $gcd⁡(x,n)≠1$, the inverse does not exist.

📌 Finding Modular Inverses in Mod 12

x	gcd⁡(x,12)	Inverse Exists?
1	1	✅ Yes
2	2	❌ No
3	3	❌ No
4	4	❌ No
5	1	✅ Yes
6	6	❌ No
7	1	✅ Yes
8	4	❌ No
9	3	❌ No
10	2	❌ No
11	1	✅ Yes

Even if $ℤ_{12}$ has some inverses, it is not a field, as not all of them have one.

Teorema Chino del Resto

También conocido como Teorema de Euler

a ∈ ℤ
m ∈ ℕ⁺

si mcd(a,m)=1

aᶲ⁽ ºͫ⁾= 1 mod m
Φ(m) : funcion de Euler

Pequeño Teorema de Fermat

Si n es un número primo que no divide al número a entonces:

aⁿ⁻¹ ≡1 mod n

Teorema de Wilson

Si n es un número primo, entonces

(n-1)! ≡ -1 mod n

Enteros módulo p

Se representan

ℤ/p
a≡ b mod p ⟺ ∃𝑘∈ ℤ, a-b = 𝑘p


ℤ/p= {0,1,2,…,(p-1)}

Tma de congruencia

in modulo n:
a is congruent to r
⟺
n∣(a-r)
⟺
a ≡ r 	mod n
r̅={r, r±n, r±n²…}

a͞+͞b = a̅ + b̅