1.md

Invertibility and Divisibility in Modular Arithmetic

In the context of modular arithmetic, we often deal with the concepts of invertibility and divisibility. Understanding these concepts is crucial in various areas of mathematics and computer science and cryptography.

Invertibility in $ℤ_n$

In $ℤ_n$, a non-zero integer a is invertible if there exists another integer b such that their product is congruent to 1 modulo n. In other words, a has a multiplicative inverse b in $ℤ_n$ if $a\cdot b ≡ 1~(\text{mod}~n)$.

This result signifies that when considering two integers, $a$ and $b$, that are coprime, i.e., they share no common divisors other than 1, then $a$ can be "inverted" within $ℤ_b$, and $b$ can be inverted within $ℤ_a$.

In Rust, we can use our Euclidean algorithm implementation to define another two functions: coprime and is_invertible. Here's an example implementation in Rust:

fn coprime(a: i32, b: i32) -> bool {
    return gcd(a, b) == 1;
}

And then, given the coprime-invertibility relationship, we can define is_invertible by calling coprime:

fn is_invertible(a: i32, modulus: i32) -> bool {
    return coprime(a, modulus);
}

It can be observed that the integer $i$ is unable to divide $(i + 1)$, with the remainder always being 1. This implies that any pair of values $(i, i + 1)$ are coprime, as they do not share any common divisors other than 1. Consequently, $i$ is invertible in $ℤ_{i + 1}$, property that can be used to test our implementation of is_invertible:

let mut i = 1;
while i < 1000000 {
    assert_eq!(is_invertible(i, i + 1), true);
    i += 1;
}

Divisibility in $ℤ_n$

In $ℤ_n$, an integer $a$ is divisible by another integer $b$ if their congruence modulo $n$ is equal to 0. In other words, $a$ is divisible by $b$ in $ℤ_n$ if $a\cdot b ≡ 0~(\text{mod}~n)$.