02.3 Modular Arithmetic

Definition

Let $m>1$ be the modulus, an integer The set of all integers congruent to $a\mathrm{mod}m$ is called the congruence class of $a$ modulo $m$ It is denoted as $[a{]}_m$

Definition

The set of all congruence classes modulo $m$ is denoted $\mathbb{Z}/m\mathbb{Z}$ (read $\mathbb{Z}$ mod $m$)

There are some elements for which there exists a multiplicative inverse

$$[a{]}_m[b{]}_m=[b{]}_m[a{]}_m=[1{]}_m$$

Which is denoted as $([a{]}_m{)}^{-1}$, if it is unique and exists

Theorem

In $\mathbb{Z}/m\mathbb{Z}$, we have the equivalent statements:

1. $[a{]}_m$ has the inverse
2. For all $[b{]}_m$ $[a{]}_{m}x=[b{]}_m$ has a unique solution
3. There exists $[b{]}_m$ such that $[a{]}_{m}x=[b{]}_m$ has a unique solution

Theorem

Let $m>1$ be an integer The element $[a{]}_m\in \mathbb{Z}/m\mathbb{Z}$ has a unique multiplicative inverse ⇐> $\gcd (a,m)=1$

Theorem

If $\rho$ is prime, all elements of $\mathbb{Z}/\rho \mathbb{Z}$ except $[0{]}_{\rho }$ have a multiplicative inverse

Euclid and Bézout

Theorem (Euclid)

Let $a,b$ be non-zero integers. Then for $k$

$$\gcd (a,b)=\gcd (b,a-kb)$$

This means that we can make a simple gcd algorithm:

Algorithm

fn gcd(a: i32, b: i32) -> i32 {
	return if a < b {
		gcd(b, a)
	} else if b == 0 {
		a
	} else {
		gcd(b, a % b)
	}
}

Theorem (Bézout)

Let $a$ and $b$ be integers, $\ne 0$ There are integers $u$ and $v$ such that

$$\gcd (a,b)=au+bv$$

With that, we can draw another algorithm:

Algorithm

fn euclid(a: i32, b: i32) -> (i32, i32, i32) {
	return if a < b {
		euclid(b, a)
	} else if b == 0 {
		(1, 0, a)
	} else {
		let q: i32 = a / b;
		let r: i32 = a % b;
		let (u, v, d) = euclid(b, r);
		(v, u - v * q, d) 
	}
}

Corollary

$\gcd (a,m)=1$ ⇐> there exists integers $u$ and $v$ s.t $au+mv=1$

02.4 Commutative Groups