Modular Arithmetic

Modular arithmetic is a fascinating branch of mathematics that deals with numbers “wrapping around” when they reach a certain value, known as the modulus. Here are the key concepts:
Definition:
In modular arithmetic, we work with integers and consider their remainders when divided by a fixed quantity (the modulus).
Think of it like a clock: after reaching 12 hours, the clock “wraps around” to 1.
The modern approach to modular arithmetic was developed by Carl Friedrich Gauss

The Modulus
If $a$  is an integer and $n$ is a positive integer, we define $ a \: mod \: n $ to be the remainder when $a$ is divided by $n$ . The integer is called the modulus. Thus, for any integer ,

$$a = qn+r \quad  0 \le r \lt n \quad q=\lfloor a/n \rfloor$$

$$r= a - \lfloor a/n \rfloor .n $$
Example:
$11 \: \mod \: 7 =4$ and $-11 \: \mod  \: 7=3$

Two integers $a$ and $b$ are  said to congruent modulo $n$, if $a \: \mod \: n= b \: \mod \: n$.This is written as

$$a \equiv b (\mod  n)$$
Example:
$5 \equiv 16 (\mod 11) $ and $2 \equiv 5(\mod 3)$

Note that if $ a\equiv 0 (\mod n)$, then $n|a$.

Properties of Congruences
Congruences have the following properties
1.$a \equiv b ( \mod n) $ if $n|(a-b)$
Note: If $n|(a-b)$, then$ (a-b)=kn$ for some $k$. So we can write $a=b+kn \mod n$. This implies $a \equiv b\mod n$
2.If $a \equiv b ( \mod n)$ implies $b \equiv a (\mod n)$
3.$a \equiv b( \mod n)$  and $b \equiv c (\mod n)$ imply $a \equiv c (\mod n)$

Example:
$23 \equiv 8 (\mod 5)$ implies $5|23-8$ ie; $5|15$


Modular Arithmetic Operations
Note that, by definition , the (mod ) operator maps all integers into the set of integers $\{0, 1, \ldots , (n - 1)\}$.This suggests the question: Can we perform arithmetic operations within the confines of this set? It turns out that we can; this technique is known as modular arithmetic.

Modular Addition:
Rule for modular addition: $ (a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m $

Example: 
$(15 + 17) \mod 7 = ((15 \mod 7) + (17 \mod 7)) \mod 7 = (1 + 3) \mod 7 = 4 \mod 7 $. This is same as $32\mod 7=4 \mod 7$
Proof:
Define $a \mod n=r_a$ and $b \mod n=r_b$.
Then we can write $a=j.n+r_a$ for some integer $j$  and $b=k.n+r_b$for some integer $k$.
.Then
$$(a+b) \mod n=j.n+r_a + k.n+r_b \mod n$$
$$(a+b) \mod n=r_a+r_b+j.n+k.n \mod n$$
$$(a+b) \mod n= r_a+r_b \mod n$$
$$(a+b) \mod n=(a \mod n  +b \mod n )\mod n$$

Modular Subtraction:
Rule for modular addition: $ (a - b) \mod m = ((a \mod m) - (b \mod m)) \mod m $

Example: 
$(17- 15) \mod 7 = ((17\mod 7) - (15\mod 7)) \mod7 = (3- 1) \mod 7 = 2 \mod 7 $. This is same as $2\mod 7$
Proof:
Define $a \mod n=r_a$ and $b \mod n=r_b$.
Then we can write $a=j.n+r_a$ for some integer $j$  and $b=k.n+r_b$for some integer $k$.
.Then
$$(a-b) \mod n=j.n+r_a -( k.n+r_b) \mod n$$
$$(a-b) \mod n=r_a-r_b+(j.n- k.n) \mod n$$
$$(a-b) \mod n= r_a-r_b \mod n$$
$$(a-b) \mod n=(a \mod n -b \mod n )\mod n$$

Modular Multiplication:
Rule for modular multiplication:  $(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$ 

Example: 
$((12 \cdot 13) \mod 5 = ((12 \mod 5) \cdot (13 \mod 5)) \mod 5 = (2 \cdot 3) \mod 5 = 6 \mod 5 = 1)$
Proof:
Define $a \mod n=r_a$ and $b \mod n=r_b$.
Then we can write $a=j.n+r_a$ for some integer $j$  and $b=k.n+r_b$for some integer $k$.
.Then
$$(a\cdot b) \mod n=(j.n+r_a ) \cdot ( k.n+r_b) \mod n$$
$$(a\cdot b) \mod n=r_a \cdot r_b+(j.n \cdot k.n + j.n \cdot r_b + r_a \cdot k.n) \mod n$$
$$(a\cdot b) \mod n= r_a \cdot r_b \mod n$$
$$(a\cdot b) \mod n=(a \mod n \cdot b \mod n )\mod n$$

Modular Exponentiation:
Finding $(a^b \mod m)$ is modular exponentiation.
It can be done recursively or iteratively.

Example: 
For $a = 15,b = 2$ , and $m = 7$, $(15^2) \mod 7 = 225 \mod 7 = 1\mod 7$
This is same as $(15 \mod 7 \cdot 15 \mod 7 ) \mod 7=1\cdot 1 \mod 7=1\mod 7$

To find To find $11^7 \mod 13$, we can proceed iteratively as follows:
$11^2 = 121 \equiv 4 (\mod 13)$

$11^4 = (11^2)^2 \equiv 4^2 \equiv 3 (mod 13)$

Thus,
$11^7 =11\cdot 11^2 \cdot 11^4=11 * 4 * 3 \equiv 132 \equiv  2 (mod 13)$

Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic.
Table below provides an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward, and there is a regular pattern to the matrix. Both matrices are symmetric about the main diagonal in conformance to the commutative property of addition and multiplication. As in ordinary addition, there is an additive inverse, or negative, to each integer in modular arithmetic. In this case, the negative of an integer $x$ is the integer $y$ such that $(x+y) \mod 8=0$.
To find the additive inverse of an integer in the left-hand column,scan across the corresponding row of the matrix to find the value 0; the integer at the top of that column is the additive inverse; thus,$(2+6)\mod 8 =0$. 

Similarly, the entries in the multiplication table are straightforward. In ordinary arithmetic, there is a multiplicative inverse, or reciprocal, to each integer. In modular arithmetic mod 8, the multiplicative inverse of $x$ is the integer $y$ such that .$x\cdot y \mod 8=1 \mod 8$.

Now, to find the multiplicative inverse of an integer from the multiplication table, scan across the matrix in the row for that integer to find the value 1; the integer at the top of that column is the multiplicative inverse; thus, $3\cdot 3=1 \mod 8$. Note that not all integers mod 8 have a multiplicative inverse.In general, an integer has a multiplicative inverse in $\mathbb{Z}_n$ ,if that integer is relatively prime to $n$.Table below  shows that the integers 1, 3, 5, and 7 have a multiplicative inverse in ; but 2, 4, and 6 do not.


There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that (as in ordinary arithmetic) we can write the following:
$a+b\: \equiv a+c (\mod n) \: then\: b \equiv c (\mod n)$
Example:
$5+23\: \equiv 5+7 (\mod 8) \: then\: 23 \equiv 7 (\mod 8)$

The above equation  is consistent with the existence of an additive inverse. Adding the additive inverse of to both sides of Equation, we have
$-a+b+b \equiv -a+a+c (\mod n)$
$b \equiv c (\mod n)$
However, the following statement is true only with the attached condition:
If $a \times b \equiv a \times c \mod n$ then $b \equiv c \mod n$. If $a$ is relatively prime to $n$.

Recall that two integers are relatively prime if their only common positive integer factor is 1.ie;$gcd(a,n)=1$



Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more