⇒ 𝑎|𝑏𝑚

Modular Arithmetic • Theorem 3: If 𝒂|𝒃 and 𝒂|𝒄 then 𝒂|(𝒃𝒎 ± 𝒄𝒏)

Proof: 𝑎|𝑏 ⇒ 𝑏 = 𝑎𝑘1 ⇒ 𝑚𝑏 = 𝑚𝑎𝑘1
Unit V
𝑎|𝑐 ⇒ 𝑐 = 𝑎𝑘2 ⇒ 𝑛𝑐 = 𝑛𝑎𝑘2
Division Algorithm
𝑚𝑏 ± 𝑛𝑐 = 𝑎(𝑚𝑘1 ± 𝑛𝑘2 ) =
For any integers 𝑎 and 𝑏 > 0, there exists 𝑞, 𝑟 such
= 𝑎𝑘 (let 𝑚𝑘1 ± 𝑛𝑘2 = 𝑘)
that
⇒ 𝑎|(𝑚𝑏 ± 𝑛𝑐)
𝑎 = 𝑏𝑞 + 𝑟, 0 ≤ 𝑟 < 𝑏
if 𝑟 = 0, i.e., 𝑎 = 𝑏𝑞 then 𝑎 is said to be divisible by
• Greatest Common Divisor
𝑏. It can be written
An integer 𝑑 is said to be the greatest common
𝒃|𝒂
divisor of 𝑎 and 𝑏 if
It can be read as
1) 𝑑|𝑎 and 𝑑|𝑏
• 𝑏 divides a
2) If 𝑐 is any integer that divides 𝑎 and 𝑏 then 𝑐|𝑑
• 𝑎 is divisible by 𝑏
denoted by 𝐠𝐜𝐝(𝒂, 𝒃) = 𝒅 or (𝒂, 𝒃) = 𝒅
• 𝑏 is the divisor of 𝑎
• If (𝑎, 𝑏) = 1 then 𝑎 and 𝑏 are said to be relatively
• 𝑏 is a factor of 𝑎
prime
The proper divisors of a positive integer N are those
numbers, other than N itself, that divide N without
• Theorem 4: If (𝑎, 𝑏) = 𝑑, then 𝑑 can be written
remainder.
as a linear combination of 𝑎 and 𝑏.
• For 𝑁 > 1, they will always include 1, but
i.e., 𝑑 = 𝑠𝑎 + 𝑡𝑏
for 𝑁 == 1 there are no proper divisors.
Examples
• Theorem 5: If 𝒂|𝒃𝒄 and (𝒂, 𝒃) = 𝟏 then 𝒂|𝒄
The proper divisors of 6 are 1, 2, and 3.
Proof: (𝑎, 𝑏) = 1 ⇒ 1 = 𝑠𝑎 + 𝑡𝑏 (by Theorem 4)
The proper divisors of 100 are 1, 2, 4, 5, 10, 20,
𝑐 = 𝑠𝑎𝑐 + 𝑡𝑏𝑐 (multiply 𝑐 on
25, and 50.
both sides)
If 𝑎|𝑏𝑐 then 𝑎|𝑡𝑏𝑐 also 𝑎|𝑠𝑎𝑐 (by Theorem 2)
• 𝑎|𝑎 → Divisibility is Reflexive
⇒ 𝑎|(𝑠𝑎𝑐 + 𝑡𝑏𝑐) ⇒ 𝑎|𝑐
• 𝑎|𝑏 but 𝑏 ∤ 𝑎 → Divisibility is not symmetric

• Theorem 6: If 𝒂|𝒄 and 𝒃|𝒄, (𝒂, 𝒃) = 𝟏 then 𝒂𝒃|𝒄

• Theorem 1: If 𝒂|𝒃 and 𝒃|𝒄 then 𝒂|𝒄
Proof: (𝑎, 𝑏) = 1, 𝑎|𝑐 ⇒ 𝑐 = 𝑘1 𝑎 -(1) and
Proof: 𝑎|𝑏 ⇒ 𝑏 = 𝑎𝑘1
𝑏|𝑐 ⇒ 𝑐 = 𝑘2 𝑏 -(2)
𝑏|𝑐 ⇒ 𝑐 = 𝑏𝑘2
⇒ 𝑏|𝑐 = 𝑏|𝑘1 𝑎 , also we have
𝑐 = 𝑎𝑘1 𝑘2 = 𝑎𝑘 (let 𝑘1 𝑘2 = 𝑘)
(𝑎, 𝑏) = 1

• Theorem 2: If 𝒂|𝒃 then 𝒂|(𝒃𝒎) Theorem 5 ⇒ 𝑏|𝑘1 ⇒ 𝑘1 = 𝑏𝑘3

Proof: 𝑎|𝑏 ⇒ 𝑏 = 𝑎𝑘1 (1)⇒ 𝑐 = 𝑘1 𝑎 = (𝑏𝑘3 )𝑎 = (𝑎𝑏)𝑘3

⇒ 𝑏𝑚 = 𝑎𝑚𝑘1 = 𝑎𝑘(let 𝑚𝑘1 = 𝑘) ⇒ 𝑎𝑏|𝑐

 Modular Arithmetic

• Theorem 7: If (𝒂, 𝒃) = 𝟏 = (𝒂, 𝒄) then ⇒ (𝑎𝑛 , 𝑏 𝑛 ) = 1

(𝒂, 𝒃𝒄) = 𝟏 • Theorem 10: If (𝒂, 𝒃) = 𝟏 then (𝒂 + 𝒃, 𝒂 − 𝒃)is
Proof: (𝑎, 𝑏) = 1 ⇒ 𝑠𝑎 + 𝑡𝑏 = 1 -(1) and either 1 or 2
(𝑎, 𝑐) = 1 ⇒ 𝑢𝑎 + 𝑣𝑐 = 1 -(2) Proof: Let 𝑑|𝑎 + 𝑏 ⇒ 𝑎 + 𝑏 = 𝑑𝑘1
(1)x(2) ⇒ (𝑠𝑎 + 𝑡𝑏)(𝑢𝑎 + 𝑣𝑐) = 1 𝑑|𝑎 − 𝑏 ⇒ 𝑎 − 𝑏 = 𝑑𝑘2
⇒ (𝑠𝑎(𝑢𝑎 + 𝑣𝑐) + 𝑡𝑏 ⋅ 𝑢𝑎 + 𝑡𝑣𝑏𝑐) = 1 ⇒ 2𝑎 = 𝑑(𝑘1 + 𝑘2 ) & 2𝑏 = 𝑑(𝑘1 − 𝑘2 )
⇒ (𝑠𝑢𝑎 + 𝑠𝑣𝑐 + 𝑡𝑏 ⋅ 𝑢)𝑎 + 𝑡𝑣 ⋅ 𝑏𝑐 = 1 ⇒ 𝑑|2𝑎 & 𝑑|2𝑏
⇒ 𝑘1 𝑎 + 𝑘2 𝑏𝑐 = 1 Since (𝑎, 𝑏) = 1, 𝑑 ∤ 𝑎 & 𝑑 ∤ 𝑏 ⇒ 𝑑|2
⇒ (𝑎, 𝑏𝑐) = 1 Hence 𝑑 must be 1 or 2.

• Theorem 8: If (𝒂, 𝒃) = 𝟏 and if 𝒄|𝒂 and 𝒅|𝒃 • Theorem 11: Every integer 𝒏 > 𝟏 is either a
then (𝒄, 𝒅) = 𝟏 prime number or a product of prime numbers
Proof: (𝑎, 𝑏) = 1 ⇒ 𝑠𝑎 + 𝑡𝑏 = 1 -(1) and (The Fundamental Theorem of Arithmetic)
𝑐|𝑎 ⇒ 𝑎 = 𝑐𝑘1 -(2) Proof: If 𝑛 is a prime, the theorem is proved. If
𝑑|𝑏 ⇒ 𝑏 = 𝑑𝑘2 -(3) 𝑛 ≠ 1 and 𝑛 is not a prime, then 𝑛 = 𝑎𝑏, for some
Substituting (3,2) in (1) ⇒ 𝑠𝑐𝑘1 + 𝑡𝑑𝑘2 = 1 𝑎, 𝑏 ∈ 𝑍 ∋ 0 < 𝑎 < 𝑛, 0 < 𝑏 < 𝑛.
⇒ (𝑠𝑘1 )𝑐 + (𝑡𝑘2 )𝑑 = 1 Let 𝑃(𝑛) stands for the proposition that 𝑛 can be
⇒ (𝑐, 𝑑) = 1 factorized as stated in the theorem.
Let us assume that 𝑃(𝑘) is true for 𝑘 < 𝑛. Then
• Theorem 9: If (𝒂, 𝒃) = 𝟏 then (𝒂𝒏 ,𝒃 𝒏)
= 𝟏 for 𝑃(𝑎) and 𝑃(𝑏) are true, i.e., 𝑎 and 𝑏 can be
all 𝒏 ≥ 𝟏 factorized as a product of positive prime numbers.
Proof: (𝑎, 𝑏) = 1 ⇒ 𝑠𝑎 + 𝑡𝑏 = 1 -(1) i.e., 𝑎 = 𝑝1 𝑝2 … 𝑝𝑟 and 𝑏 = 𝑞1 𝑞2 … 𝑞𝑟 .
(𝑠𝑎 + 𝑡𝑏)2𝑛−1 = 1 ⇒ 𝑛 = 𝑎𝑏 = (𝑝1 𝑝2 … 𝑝𝑟 )(𝑞1 𝑞2 … 𝑞𝑟 )
𝟐𝒏 − 𝟏 (𝒂𝒔)𝟐𝒏−𝟏 𝟐𝒏 − 𝟏 (𝒂𝒔)𝟐𝒏−𝟐 (𝒃𝒕)𝟏 Hence 𝑃(𝑛) is true, i.e., the theorem is proved.
( ) +( )
𝟎 𝟏
𝟐𝒏 − 𝟏 (𝒂𝒔)𝟐𝒏−𝟑 (𝒃𝒕)𝟐
+( ) +⋯ • Theorem 12: There are infinitely many prime
𝟐
𝟐𝒏 − 𝟏 (𝒂𝒔)𝒏 (𝒃𝒕)𝒏−𝟏 numbers
+( )
𝒏−𝟏 Proof: Let there be a finite number of primes
2𝑛 − 1 (𝑎𝑠)𝑛−1 (𝑏𝑡)𝑛 (𝑝1 , 𝑝2 , … 𝑝𝑛 )
+( ) +⋯
𝑛
2𝑛 − 1 (𝑏𝑡)2𝑛−1 Consider 𝑝 = 𝑝1 𝑝2 … 𝑝𝑛 + 1 > 𝑝𝑖 ∀𝑖
+( ) =1
2𝑛 − 1 Since there are finite primes and 𝑝 is greater than
Here first 𝑛 terms are divisible by 𝑎𝑛 and last 𝑛 all, we can conclude that 𝒑 is not prime.
𝑛
terms are divisible by 𝑏 , hence above equation 𝑝
Let divide 𝑝 by 𝑝1 ⇒ 𝑝 = 𝑝2 𝑝3 … 𝑝𝑛 + 𝑝
1
1 1
can be written as
𝑎𝑛 𝑢 + 𝑏 𝑛 𝑣 = 1

 Page 1
  Modular Arithmetic

1
Clearly 𝑝 is not an integer, it is true for any 𝑝𝑖 , • Write 𝑎 in quotient remainder form (𝑎 = 𝑏 ⋅ 𝑞 +
1
𝑟)
hence none of the 𝑝𝑖 is a factor of 𝑝.
• Find GCD(B,R) using the Euclidean Algorithm
𝑝 is a number that can not be factorized by the
since GCD(A,B) = GCD(B,R)
prime numbers hence, from Theorem 11, 𝒑 must
be prime
𝑝 is prime and not prime. Which is a contradiction.
Find the GCD of the following using the division
So our assumption is wrong. i.e., there are
algorithm
infinitely many primes.
i) 27, 87 ii) 165,418 iii) 30, 42, 70
iv) 50,90,240 v) 18,24,30,38
• Theorem 13: If a prime 𝒑 does not divide 𝒂,
i) 27, 87 𝑎 = 𝑏𝑞 + 𝑟
then (𝒑, 𝒂) = 𝟏
𝑞 𝑎 𝑏 𝑟
Proof: Let (𝑝, 𝑎) = 𝑑
3 87 27 6
⇒ 𝑑|𝑝 but 𝑝 is prime, so 𝑑 must be 1 or 𝑝 itself.
4 27 6 3
Also 𝑑|𝑎 ⇒ 𝑑 ≠ 𝑝, because 𝑝 ∤ 𝑎. ⇒ 𝑑 = 1.
2 6 3 0
3 0
• Theorem 14: If a prime 𝒑 divides 𝒂𝒃, then 𝒑|𝒂
or 𝒑|𝒃. More generally, if a prime 𝒑 divides a
ii) 165, 418 𝑎 = 𝑏𝑞 + 𝑟
product 𝒂𝟏 𝒂𝟐 … 𝒂𝒏 then 𝒑 divides at least one of
the factors 𝑞 𝑎 𝑏 𝑟
Proof: Suppose 𝑝|𝑎𝑏 and that 𝑝 ∤ 𝑎. We will 2 418 165 88
prove that 𝑝|𝑏. 1 165 88 77
From theorem 13 we have (𝑝, 𝑎) = 1, then from 1 88 77 11
Theorem 4, 1 = 𝑝𝑠 + 𝑎𝑡 7 77 11 0
𝑏 = 𝑠 𝑝𝑏 + 𝑡𝑏 𝑎 11 0
Since 𝑝|𝑠𝑝𝑏 and 𝑝|𝑎𝑏 ⇒ 𝑝|𝑡𝑏𝑎, we get 𝑝|𝑏.
Similarly, we can prove it in general for 1 ≤ 𝑖 ≤ 𝑛 iii) 30, 42, 70
using induction. Find GCD(30,42)
𝑞 𝑎 𝑏 𝑟
The Euclidean Algorithm for finding 1 42 30 12
GCD(A,B) is as follows: 2 30 12 6
• If 𝑎 = 0 then 𝐺𝐶𝐷(𝑎, 𝑏) = 𝑏, since the 2 12 6 0
𝐺𝐶𝐷(0, 𝑏) = 𝑏, and we can stop. 6 0
• If 𝐵 = 0 then 𝐺𝐶𝐷(𝑎, 𝑏) = 𝑎, since the GCD(30,42) = 6
𝐺𝐶𝐷(𝑎, 0) = 𝑎, and we can stop. Now find GCD(6,70)

 Page 2
 Modular Arithmetic

𝑞 𝑎 𝑏 𝑟
% Are m and n greater than zero?
11 70 6 4
if m <= 0 || n <= 0
1 6 4 2 res = -3;
2 4 2 0 return
2 0 end
GCD(6,70)=2
% Swap m and n if m less than n
GCD(30,42,70)=2
% to allow the algorithm to function
properly
MATLAB Code if m < n
prompt1 = "Enter the first number: "; tmp = m;
m = input(prompt1); %Get the first number m = n;
prompt2 = "Enter the second number: "; n = tmp;
n = input(prompt2); %Get the first number end
ans=euclid(m,n); %Call the recursive function
euclid % Result of modulus is zero so we have
if ans==-1 found the gcd
fprintf('Enter the numeric if mod(m,n) == 0
values\n') fprintf('GCD(%d,%d)=>',m,n);
elseif ans==-2 res = n;
fprintf('Enter the integral else
values\n') fprintf('GCD(%d,%d)=>',m,n);
elseif ans==-3 res = euclid(n,mod(m,n)); % Euclid's
fprintf('Enter the positive algorithm
values\n') end
else
fprintf('%d\n',ans) end
end

Procedure to find GCD of given numbers and

function [res] = euclid(m,n)
% Are m and n the right types?
express GCD as a linear combination of the given
if ~isnumeric(m) || ~isnumeric(n) numbers (Extended Euclidian Algorithm)
res = -1; • Take 𝑎 > 𝑏 and find GCD using the Division
return algorithm: 𝑎 = 𝑏𝑞 + 𝑟
end
• Simultaneously calculate 𝑠3 = 𝑠1 − 𝑞𝑠2 &
% Are m and n integer-like? 𝑡3 = 𝑡1 − 𝑞𝑡2 until we get the GCD
if m ~= int64(m) || n ~= int64(n) • Correspondingly obtained 𝑠2 and 𝑡2 are the
res = -2; required coefficients 𝑠 and 𝑡 such that
return;
gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏
end

 Page 3
  Modular Arithmetic

𝑐 𝑐
Let 𝑥0 = 𝑠 𝑑 and 𝑦0 = 𝑡 𝑑 such that 𝑑 = 𝑠𝑎 + 𝑡𝑏, be the
Find GCD of given numbers and express GCD as a particular solution of the Diophantine equation, the
linear combination of the given numbers general solution of the Diophantine equation is given
i) 826,1890 by
𝑎 = 1890, 𝑏 = 826 {coeff of 𝑦}
𝑞 𝑎 𝑏 𝑟 𝑠1 𝑠2 𝑠3 𝑡1 𝑡2 𝑡3 𝑥 = 𝑥0 + 𝑛
𝑑
2 1890 826 238 1 0 1 0 1 -2 {coeff of 𝑥}
𝑦 = 𝑦0 − 𝑛
3 826 238 112 0 1 -3 1 -2 7 𝑑
2 238 112 14 1 -3 7 -2 7 -16 where 𝑛 ∈ 𝑍, 𝑑 = gcd(𝑎, 𝑏).
8 112 14 0 -3 7 -59 7 -16 135
14 0 Determine whether the following LDE’s are
solvable or not:
𝒈𝒄𝒅(𝟏𝟖𝟗𝟎, 𝟖𝟐𝟔) = 𝟏𝟒; 𝒔 = 𝟕, 𝒕 = −𝟏𝟔
i) 12𝑥 + 18𝑦 = 30
⇒ 14 = 7 × 1890 + (−16) × 826
gcd(12,18)=6 and 30 is a multiple of 6. Hence given
ii) 165,418
LDE is solvable.
𝑎 = 418, 𝑏 = 165
ii) 6𝑥 + 8𝑦 = 25
𝑞 𝑎 𝑏 𝑟 𝑠1 𝑠2 𝑠3 𝑡1 𝑡2 𝑡3
gcd(6,8)=2 and 25 is not a multiple of 2. Hence
2 418 165 88 1 0 1 0 1 -2
given LDE is not solvable.
1 165 88 77 0 1 -1 1 -2 3
1 88 77 11 1 -1 2 -2 3 -5
Find the general solution of the following LDE’s:
7 77 11 0 -1 2 -15 3 -5 38
11 0
i) 𝟐𝟖𝒙 + 𝟗𝟏𝒚 = 𝟏𝟏𝟗
𝒈𝒄𝒅(𝟒𝟏𝟖, 𝟏𝟔𝟓) = 𝟏𝟏; 𝒔 = 𝟐, 𝒕 = −𝟓
𝑎 = 91, 𝑏 = 28
⇒ 11 = (2)418 + (−5)165
gcd(91,28)=7, 7|119 ⇒ given LDE has solution
Online Calculator for Extd. Euclidian Alg.
𝑞 𝑎 𝑏 𝑟 𝑠1 𝑠2 𝑠3 𝑡1 𝑡2 𝑡3
https://www.extendedeuclideanalgorithm.com/calculat
3 91 28 7 1 0 1 0 1 -3
or.php?mode=1
4 28 7 0 0 1 -4 1 -3 13
7 0
Linear Diophantine Equation(LDE)
7 = (1)91 + (−3)28
For any 𝑎, 𝑏, 𝑐 ∈ 𝑍, the simplest form of the
The particular solution of 28𝑥 + 91𝑦 = 119 is given
Diophantine equation takes the form 𝑎𝑥 + 𝑏𝑦 = 𝑐.
by
Suppose 𝑎 and 𝑏 are integers, then the Diophantine
𝑐
equation 𝑎𝑥 + 𝑏𝑦 = 𝑐 has a solution iff 𝑐 is a multiple 𝑥0 = 𝑠 = −3 × 17 = −51,
𝑑
of 𝑔𝑐𝑑(𝑎, 𝑏). 𝑐
𝑦0 = 𝑡 = 1 × 17 = 17
𝑑
⇒ 28(−51) + 91(17) = 119

 Page 4
  Modular Arithmetic

The general solution is given by

{coeff of 𝑦} MATLAB Code
𝑥 = (𝑥0 + 𝑛) = −51 + 13𝑛
𝑑 Clear clc
{coeff of 𝑥} syms x y t
𝑦 = (𝑦0 − 𝑛) = 17 − 4𝑛 assume([x y], 'integer') % assume ‘x’
𝑑
and ‘y’ are integers
𝑥 = −51 + 13𝑛; 𝑦 = 17 − 4𝑛 is the general solution eqn = 1485*x +1745*y == 15 ; % declare the
of the given LDE. equation
disp(eqn)
ii) 1485𝒙 + 𝟏𝟕𝟒𝟓𝒚 = 𝟏𝟓 c = coeffs(lhs(eqn) ,[y,x]);
r=rem(rhs(eqn),gcd(c(1),c(2)));
𝑎 = 1745, 𝑏 = 1485
if r~=0
gcd(1745,1485)=5, 5|15 ⇒ given LDE has solution disp('No Solution')
𝑞 𝑎 𝑏 𝑟 𝑠1 𝑠2 𝑠3 𝑡1 𝑡2 𝑡3 else
1 1745 1485 260 1 0 1 0 1 -1 fprintf('%d is multiple of gcd(%d,%d)=%d,
5 1485 260 185 0 1 -5 1 -1 6 hence it has
solution\n',rhs(eqn),c(1),c(2),gcd(c(1),c(2)))
1 260 185 75 1 -5 6 -1 6 -7
if rhs(eqn)~=0
2 185 75 35 -5 6 -17 6 -7 20
[xSol, ySol] = solve(eqn,[x y]); %
2 75 35 5 6 -17 40 -7 20 -47
solve for ;x’ and ‘y’
7 35 5 0 -17 40 -297 20 -47 349
xComp=xSol+t*(c(2)/gcd(c(1),c(2)));
5 0 yComp=ySol+t*(-c(1)/gcd(c(1),c(2)));
else
5 = (40)1745 + (−47)1485 xSol=c(2)/gcd(c(1),c(2));
ySol=-c(1)/gcd(c(1),c(2));
The particular solution of 1485𝑥 + 1745𝑦 = 15 is
xComp=xSol*t;
given by
yComp=ySol*t;
𝑥0 = −47 × 3 = −141; 𝑦0 = 40 × 3 = 120 end
⇒ 1485(−141) + 1745(120) = 15 fprintf(' Solution is : x=%d,
The general solution is given by y=%d\n',xSol,ySol)
{coeff of 𝑦} fprintf('General Solution [x,y]:\n')
𝑥 = (𝑥0 + 𝑛) = −141 + 349𝑛 fprintf('x=')
𝑑
disp(xComp)
{coeff of 𝑥} fprintf('y=')
𝑦 = (𝑦0 − 𝑛) = 120 − 297𝑛
𝑑 disp(yComp)
𝑥 = −141 + 349𝑛; 𝑦 = 120 − 297𝑛 is the general end

solution of the given LDE.

Online Calculator to solve LDE

https://www.math.uwaterloo.ca/~snburris/htdocs/linear.html

 Page 5
  Modular Arithmetic

residue class of 0: [0] = {… − 9, −6, −3,0,3,6,9, … }

Congruences residue class of 1: [1] = {… − 8, −5, −2,1,4,7,10, … }
Two integers 𝑎 and 𝑏 are said to be congruent modulo residue class of 2: [2] = {… − 7, −4, −1,2,5,8,11, … }
an integer 𝑚 iff 𝑚 divides 𝑎 − 𝑏 represented as
𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) Relation between Congruence and LDE
(𝑎 congruent to 𝑏 modulo 𝑚) A linear Diophantine equation 𝑎𝑥 + 𝑏𝑦 = 𝑐 can be
Example: written as 𝑎𝑥 ≡ 𝑐(𝑚𝑜𝑑 𝑏).
14 ≡ 2(𝑚𝑜𝑑 3), 2 ≡ 0(𝑚𝑜𝑑 2), 3 ≡ −1(𝑚𝑜𝑑 2)
*𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) then 𝑎 ≡ (𝑏 + 𝑘𝑚)(𝑚𝑜𝑑 𝑚), 𝑘 ∈ 𝑍 Procedure to solve linear congruences:
3 ≡ −1(𝑚𝑜𝑑 2) ⇒ 3 ≡ 1(𝑚𝑜𝑑 2) *For given congruence 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚), check
⇒ 3 ≡ 3(𝑚𝑜𝑑 2) ⇒ 3 ≡ 5(𝑚𝑜𝑑 2) … whether gcd(𝑎, 𝑚) divides 𝑚 or not if no, then there is
*If 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) then 𝑏 ≡ 𝑎(𝑚𝑜𝑑 𝑚) no incongruent solution, if yes then
*If 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) and 𝑐 ≡ 𝑑(𝑚𝑜𝑑 𝑚) then *Find the particular solution 𝑥0 to the given
• 𝑎 ± 𝑐 ≡ (𝑏 ± 𝑑)(𝑚𝑜𝑑 𝑚) congruence by converting it to LDE
2 + 3 ≡ (0 − 1)(𝑚𝑜𝑑 2) *Find the general solution for 𝑥
• 𝑎𝑐 ≡ 𝑏𝑑(𝑚𝑜𝑑 𝑚) *Then all incongruent solutions are the numbers greater
2 ⋅ 3 ≡ 0 ⋅ −1(𝑚𝑜𝑑 2) than 0 and less than 𝑚.
*If gcd(𝑐, 𝑚) = 1, and 𝑎𝑐 ≡ 𝑏𝑐(𝑚𝑜𝑑 𝑚) then 𝑎 ≡
𝑏(𝑚𝑜𝑑 𝑚). Solve the following linear congruences:
*If 𝑎𝑐 ≡ 𝑏𝑐(𝑚𝑜𝑑 𝑚𝑐) then 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚). 1) 𝟐𝟕𝒙 ≡ 𝟏𝟏(𝒎𝒐𝒅 𝟕)
12 ≡ 6(𝑚𝑜𝑑 2), gcd(3,2) = 1 Ans: gcd(27,7) = 1|7 ⇒ It has one incongruent
⇒ 4 ≡ 2(𝑚𝑜𝑑 2) ⇒ 2 ≡ 1(𝑚𝑜𝑑 1) solution.
27𝑥 + 7𝑦 = 11
Linear Congruence Particular solution 𝑥0 = −11, 𝑦0 = 44
A congruence of the form 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚), where 𝑥 is General solution 𝑥 = −11 + 7𝑛
unknown is called a linear congruence in one variable. The solutions are {… − 11, −4, 𝟑, 10 … }
So the incongruent solution is 3
The solution to linear congruence
If 𝑑 = gcd(𝑎, 𝑚) |𝑚 then linear congruence has 𝑑 2) 𝟖𝒙 ≡ 𝟓(𝒎𝒐𝒅 𝟏𝟏)
number of incongruent solutions else it has no Ans: gcd(8,11) = 1|5 ⇒ It has one incongruent
solutions. solution.
A residue of an integer 𝑎 in modulo 𝑚 is the unique 8𝑥 + 11𝑦 = 5
value of 0 ≤ 𝑟 ≤ 𝑚 − 1 such that 𝑎 = 𝑘𝑛 + 𝑟. Particular solution 𝑥0 = −20, 𝑦0 = 15
Example: for 𝑚𝑜𝑑 3, General solution is 𝑥 = −20 + 11𝑛
The solutions are {… − 20, −9, 𝟐, 13,24. . }

 Page 6
 Modular Arithmetic

So the incongruent solution is 𝟐 𝑥 = (2 ⋅ 77 ⋅ 𝑀1−1 + 3 ⋅ 55 ⋅ 𝑀2−1 + 10 ⋅ 35

3) 𝟏𝟓𝒙 ≡ 𝟏𝟐(𝒎𝒐𝒅 𝟑𝟔) ⋅ 𝑀3−1 )(𝑚𝑜𝑑 385)
Ans: gcd(15,36) = 3|12 ⇒ It has 3 incongruent To find 𝑀1−1 , 𝑀2−1 , 𝑀3−1
solutions. 𝑀1 𝑀1−1 ≡ 1(𝑚𝑜𝑑 𝑚1 ) ⇒ 77 ⋅ 𝑀1−1 ≡ 1(𝑚𝑜𝑑 5)
15𝑥 + 36𝑦 = 12 ⇒ 5𝑥 + 12𝑦 = 4 By inspection 𝑀1−1 = 3
Particular solution 𝑥0 = 20, 𝑦0 = −8 77𝑥−1
(Define in the calculator and calculate for
5
The general solution is 20 + 12𝑛
different values 𝑥 from 0 to get integer value, here for
The solutions are {… − 4, 𝟖, 𝟐𝟎, 𝟑𝟐, 4456. . }
𝑥 = 3 we will get 46, so 𝑀1−1 = 3)
So the incongruent solutions are 𝟖, 𝟐0,32
Similarly 𝑀2−1 = 6, 𝑀3−1 = 6
⇒ 𝑥 = 3552(𝑚𝑜𝑑 385)
Chinese Remainder Theorem
⇒ 𝑥 = 87(𝑚𝑜𝑑 385)
Let 𝑚1 , 𝑚2 , … 𝑚𝑛 be positive integers, such that
𝑔𝑐𝑑(𝑚𝑖 , 𝑚𝑗 ) = 1 (i.e., 𝑚𝑖 ’s are relative primes, then
2) 2𝑥 ≡ 6(𝑚𝑜𝑑 14), 3𝑥 ≡ 9(𝑚𝑜𝑑 15),
the system of linear congruences
5𝑥 ≡ 20(𝑚𝑜𝑑 60)
𝑥 = 𝑎1 (𝑚𝑜𝑑 𝑚1 )
Ans: 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 3(𝑚𝑜𝑑 5),
𝑥 = 𝑎2 (𝑚𝑜𝑑 𝑚2 )
𝑥 ≡ 4(𝑚𝑜𝑑 12)
𝑥 = 𝑎3 (𝑚𝑜𝑑 𝑚3 ) …
⇒ 𝑥 = 2908(𝑚𝑜𝑑 420)
𝑥 = 𝑎𝑛 (𝑚𝑜𝑑 𝑚𝑛 )
⇒ 𝑥 = 388(𝑚𝑜𝑑 420)
has a unique solution modulo to 𝑚1 𝑚2 𝑚3 … 𝑚𝑛 = 𝑀.
The solution to the above system of congruences is
3) 𝑥 ≡ 5(𝑚𝑜𝑑 6), 𝑥 ≡ 4(𝑚𝑜𝑑 11), 𝑥 ≡ 3(𝑚𝑜𝑑 17)
given by
𝑥 = (𝑎1 𝑀1 𝑀1−1 + 𝑎2 𝑀2 𝑀2−1 Solve the linear congruence using CRT
+ ⋯ 𝑎𝑛 𝑀𝑛 𝑀𝑛−1 )(𝑚𝑜𝑑 𝑀) 1)𝟏𝟕𝒙 ≡ 𝟗(𝒎𝒐𝒅 𝟖𝟒)
where 𝑀𝑖 = 𝑀/𝑚𝑖 . Since 84 = 3 ⋅ 4 ⋅ 7, given congruence is equivalent to
the system
Solve the following system of linear congruences 17𝑥 ≡ 9(𝑚𝑜𝑑 3), 17𝑥 ≡ 9(𝑚𝑜𝑑 4), 17𝑥
using CRT:
≡ 9(𝑚𝑜𝑑 7)
1) 𝑥 ≡ 2(𝑚𝑜𝑑 5), 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 10(𝑚𝑜𝑑 11)
Multiplying 17−1 on both side
Ans: Given 𝑎1 = 2, 𝑎2 = 3, 𝑎3 = 10, 𝑚1 = 5, 𝑚2 =
𝑥 ≡ 0(𝑚𝑜𝑑 3), 𝑥 ≡ 1(𝑚𝑜𝑑 4), 𝑥 ≡ 6(𝑚𝑜𝑑 7)
7, 𝑚3 = 11
Solve using CRT: 𝑥 ≡ 69(𝑚𝑜𝑑 84)
⇒ 𝑀 = 𝑚1 𝑚2 𝑚3 = 5 ⋅ 7 ⋅ 11 = 385
𝑀 385
⇒ 𝑀1 = = = 77, 𝑀2 = 55, 𝑀3 = 35 Online Calculator to solve sys. of cong. using CRT
𝑚1 5
https://www.omnicalculator.com/math/chinese-
𝑥 = (𝑎1 𝑀1 𝑀1−1 + 𝑎2 𝑀2 𝑀2−1 + 𝑎3 𝑀3 𝑀3−1 )(𝑚𝑜𝑑 𝑀)
remainder

 Page 7
  Modular Arithmetic

MATLAB Code ⇒ 3240 ≡ 1(𝑚𝑜𝑑 17)

x = crt([a1 a2 a3],[m1 m2 m3]) ⇒ 3240 37 ≡ 37 (𝑚𝑜𝑑 17)
⇒ 3247 ≡ 37 (𝑚𝑜𝑑 17)
Now find the remainder when 37 is divided by 17
Fermat's little theorem (FLT) 2187
(37 = 2187, = 128. # ⇒ 2187 − 128 ⋅ 17 = 11)
𝑝−1 17
Let 𝑝 is a prime, and 𝑔𝑐𝑑(𝑎, 𝑝) = 1, then 𝑎 ≡
i.e., 11⇒ 37 ≡ 11(𝑚𝑜𝑑 17)
1(𝑚𝑜𝑑 𝑝).
By transitivity property 3247 ≡ 11(𝑚𝑜𝑑 17)
Proof: By division algorithm,
So the remainder is 11
𝑎 = 𝑝𝑞 + 𝑟, 0 ≤ 𝑟 ≤ 𝑝 − 1
(iii) When 𝟏𝟔𝟓𝟑 is divided by 7.
Given 𝑝 is prime and 𝑎 is any integer such that 𝑝 ∤ 𝑎
Sol: 𝑝 = 7, 𝑝 − 1 = 6
i.e., gcd(𝑎, 𝑝) = 1 ⇒ 1 ≤ 𝑟 ≤ 𝑝 − 1
By FLT, 167 ≡ 1(𝑚𝑜𝑑 7)
Then
⇒ (167 )7 ≡ 17 (𝑚𝑜𝑑 7)
gcd(2𝑎, 𝑝) = 1,
⇒ 1649 ≡ 1(𝑚𝑜𝑑 7)
gcd(3𝑎, 𝑝) = 1
⇒ 1649 164 ≡ 164 (𝑚𝑜𝑑 7)
… gcd((𝑝 − 1)𝑎, 𝑝) = 1
⇒ 1653 ≡ 164 (𝑚𝑜𝑑 7)
Hence
Now find the remainder when 164 is divided by 7
gcd(𝑎 ⋅ 2𝑎 … (𝑝 − 1)𝑎) , 𝑝) = 1 65536
(164 = 65536, = 9362. # ⇒ 65536 − 9362 ⋅
i.e., 𝑎 ⋅ 2𝑎 … (𝑝 − 1)𝑎 ≡ 1 ⋅ 2 ⋅ 3 … (𝑝 − 1)(𝑚𝑜𝑑 𝑝) 7

⇒ 𝑎𝑝−1 (1 ⋅ 2 ⋅ 3 … (𝑝 − 1)) 7 = 2)
i.e., 2⇒ 164 ≡ 2(𝑚𝑜𝑑 7)
≡ 1 ⋅ 2 ⋅ 3 … (𝑝 − 1)(𝑚𝑜𝑑 𝑝)
⇒ 𝑎𝑝−1 ≡ 1(𝑚𝑜𝑑 𝑝) By transitivity property 1653 ≡ 2(𝑚𝑜𝑑 7)
So the remainder is 2
Using Fermat’s theorem, find the remainder
Solve the following Linear Congruences using FLT
(i) When 𝟕𝟐𝟎𝟎𝟏 is divided by 5.
1) 𝟏𝟐𝒙 ≡ 𝟔(𝒎𝒐𝒅 𝟕)
Sol: 𝑝 = 5, 𝑝 − 1 = 4
Sol: Since gcd(12,7)=1, 127−1 = 126 ≡ 1(𝑚𝑜𝑑 7)
By FLT, 74 ≡ 1(𝑚𝑜𝑑 5)
⇒ 1 ≡ 126 (𝑚𝑜𝑑 7)
⇒ (74 )500 ≡ 1500 (𝑚𝑜𝑑 5)
⇒ 𝑥 ≡ 126 𝑥(𝑚𝑜𝑑 7)
⇒ 72000 ≡ 7(𝑚𝑜𝑑 5)
⇒ 𝑥 ≡ 125 12𝑥(𝑚𝑜𝑑 7)
⇒ 72000 ≡ 2(𝑚𝑜𝑑 5)
So the remainder is 2. ⇒ 𝑥 ≡ 125 6(𝑚𝑜𝑑 7)
Now take 125 ≡ 55 (𝑚𝑜𝑑 7)
(ii) When 𝟑𝟐𝟒𝟕 is divided by 17.
Sol: 𝑝 = 17, 𝑝 − 1 = 16 ⇒ 55 = (52 )2 5, but 25 ≡ 4(𝑚𝑜𝑑 7)

By FLT, 316 ≡ 1(𝑚𝑜𝑑 17) ⇒ 55 ≡ (4)2 × 5(𝑚𝑜𝑑 7)

⇒ (316 )15 ≡ 115 (𝑚𝑜𝑑 17) ⇒ 55 ≡ 80(𝑚𝑜𝑑 7) ⇒ 55 ≡ 3(𝑚𝑜𝑑 7)

 Page 8
 Modular Arithmetic

⇒ 𝑥 ≡ 3 × 6(𝑚𝑜𝑑 7) If 𝒏 = 𝒑𝒒 = 𝟏𝟗𝟗𝟑𝟗 and 𝝓(𝒏) = 𝟏𝟗𝟔𝟓𝟔 , find 𝒑 and

⇒ 𝑥 ≡ 4(𝑚𝑜𝑑 7) 𝒒 such that 𝒈𝒄𝒅(𝒑, 𝒒) = 𝟏.
2) 𝟒𝒙 ≡ 𝟏𝟏(𝒎𝒐𝒅 𝟏𝟗) Sol: 𝜙(𝑝𝑞) = (𝑝 − 1)(𝑞 − 1) = 𝑝𝑞 − (𝑝 + 𝑞) + 1
Sol: Since gcd(4,19)=1, 419−1 = 418 ≡ 1(𝑚𝑜𝑑 19) ⇒ 𝜙(𝑛) = 𝑛 − (𝑝 + 𝑞) + 1
⇒ 1 ≡ 418 (𝑚𝑜𝑑 19) ⇒ 19656 = 19939 − (𝑝 + 𝑞) + 1
⇒ 𝑥 ≡ 418 𝑥(𝑚𝑜𝑑 19) ⇒ 𝑝 + 𝑞 = 284
17
⇒ 𝑥 ≡ 4 4𝑥(𝑚𝑜𝑑 19) Now we have a product and the sum of two numbers,
⇒ 𝑥 ≡ 417 11(𝑚𝑜𝑑 19) thus (𝑥 − 𝑝)(𝑥 − 𝑞) = 𝑥 2 − (𝑝 + 𝑞)𝑥 + 𝑝𝑞 = 0
Now take ⇒ 𝑥 2 − 284𝑥 + 19939 = 0
417 = (43 )5 42 , but 43 = 64 ≡ 7(𝑚𝑜𝑑 19) ⇒ (𝑥 − 157)(𝑥 − 127) = 0
⇒ 417 = (43 )5 16 ≡ 75 16(𝑚𝑜𝑑 19) ⇒ 𝑝 = 157, 𝑞 = 127
⇒ 417 ≡ (72 )2 7 × 16(𝑚𝑜𝑑 19)
(72 = 49 ≡ 11(𝑚𝑜𝑑 19) Euler's Theorem
⇒4 17 2
≡ 11 × 112(𝑚𝑜𝑑 19) If 𝑔𝑐𝑑(𝑎, 𝑛) = 1, then 𝑎𝜙(𝑛) ≡ 1(𝑚𝑜𝑑 𝑛). Here 𝜙(𝑛)
⇒ 417 ≡ 2057(𝑚𝑜𝑑 19) is Euler's totient function.
⇒ 417 ≡ 5(𝑚𝑜𝑑 19) Proof: Given 𝑛 be a positive integer and 𝑎 is any
⇒ 𝑥 ≡ 5 × 11(𝑚𝑜𝑑 19) integer such that gcd(𝑎, 𝑛) = 1. Let 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) be
⇒ 𝑥 ≡ 55(𝑚𝑜𝑑 19) the least positive residues 𝑚𝑜𝑑 𝑛 that are relatively
⇒ 𝑥 ≡ 17(𝑚𝑜𝑑 19) prime to 𝑛.
Euler’s Totient function Since gcd(𝑎, 𝑛) = 1, the integers 𝑎𝑎1 , 𝑎𝑎2 … 𝑎𝑎𝜙(𝑛)
Euler’s Totient function 𝜙(𝑛) for an input 𝑛 is the are congruent to 𝑚𝑜𝑑 𝑛 to 𝑎′1 , 𝑎′2 … 𝑎′𝜙(𝑛)
count of numbers in {1, 2, 3, … , 𝑛 − 1} that are 𝑎𝑎1 ≡ 𝑎1′ (𝑚𝑜𝑑 𝑛)
relatively prime to 𝑛, i.e., the numbers whose GCD 𝑎𝑎1 ≡ 𝑎1′ (𝑚𝑜𝑑 𝑛)
(Greatest Common Divisor) with 𝑛 is 1. ⋮
Example: 𝑎𝑎𝜙(𝑛) ≡ ′
𝑎𝜙(𝑛) (𝑚𝑜𝑑 𝑛)
𝜙(5) = 4 Hence
gcd(1, 5) is 1, gcd(2, 5) is 1, gcd(3, 5) =1 and gcd(4, 5) ′
𝑎𝑎1 ⋅ 𝑎𝑎2 … 𝑎𝑎𝜙(𝑛) ≡ 𝑎1′ 𝑎2′ … 𝑎𝜙(𝑛) (𝑚𝑜𝑑 𝑛)
is 1.
⇒ 𝑎𝜙(𝑛) (𝑎1 𝑎2 … 𝑎𝜙(𝑛) ) ≡ (𝑎1 𝑎2 … 𝑎𝜙(𝑛) )(𝑚𝑜𝑑 𝑛)
𝜙(12) = 4
1,5,7,11 are relatively prime to 12 ⇒ 𝑎𝜙(𝑛) ≡ 1(𝑚𝑜𝑑 𝑛)
So in general, if 𝑝 is prime then 𝜙(𝑝) = 𝑝 − 1 Example
𝜙(12) = 4, so if 𝑔𝑐𝑑(𝑎, 12) = 1,
• If 𝑝, 𝑞 are coprime(i.e., gcd(𝑝, 𝑞) = 1) then
then 𝑎4 ≡ 1(𝑚𝑜𝑑 12).
𝜙(𝑝𝑞) = 𝜙(𝑝)𝜙(𝑞)
• If 𝑝, 𝑞 are coprime ⇒ 𝜙(𝑝𝑞) = (𝑝 − 1)(𝑞 − 1)

 Page 9
  Modular Arithmetic

Wilson’s Theorem o Choose 𝑗 ∋ 1 < 𝑗 < 𝜙(𝑛), gcd(𝑗, 𝜙(𝑛)) = 1, here

If 𝑝 is a prime then (𝑝 − 1)! + 1 ≡ 0(𝑚𝑜𝑑 𝑝) let it be 3, ⇒ 𝑗 = 3
Example o Send (𝑛, 𝑗) to 𝑨
𝑝 = 7 ⇒ 6! + 1 = 721 ≡ 0(𝑚𝑜𝑑 7) 𝑘𝜙(𝑛)+1
o Now calculate 𝑑 = = 2011 (Secrete Key)
𝑗
where 𝑘 can be anything such that 𝑑 ∈ 𝑍.
RSA Algorithm
▪ Now B has to convert the message into numeric
RSA is a public-key cryptosystem that is widely used
format(a=097, b=098,… A=065,… space=032) gives
for secure data transmission. It is also one of the oldest.
077 111 100 117 108 097 114 032 065 114 105 116
The acronym "RSA" comes from the surnames of Ron
104 109 101 116 105 099 032 105 110 032 099 114
Rivest, Adi Shamir and Leonard Adleman, who
121 112 116 111 103 114 097 112 104 121
publicly described the algorithm in 1977.
▪ Now encrypt the message and find Cipher text
𝑐 = 𝑚𝑗 (𝑚𝑜𝑑 𝑛) and then send 𝑐 to A
Algorithm
3118 1132 2487 589 2658 2716 2473 1498 2576 2473
• Choose any two prime numbers, 𝑝1 , 𝑝2
635 523 2271 451 1518 523 635 929 1498 635 2025
• Find the product of 𝑝1 and 𝑝2 , 𝑛 = 𝑝1 𝑝2
1498 929 2473 1679 905 523 1132 1404 2473 2716
• Calculate 𝜙(𝑛) = (𝑝1 − 1)(𝑝2 − 1)
905 2271 1679
• Choose any random integer 𝑗 called as public key,
▪ Now A will decode the message using the private key
such that
that he has already, i.e.,
1 < 𝑗 < 𝜙(𝑛), & gcd(𝑗, 𝜙(𝑛)) = 1
𝑐 𝑑 (𝑚𝑜𝑑 𝑛)
𝑘𝜙(𝑛)+1
• Calculate private key 𝑑 = Gives the original message 𝑚
𝑗

• Calculate the Cipher text (encrypted message) 𝑐 = Note: Here (𝑛, 𝑗) can be seen by everyone, only who
𝑚𝑗 (𝑚𝑜𝑑 𝑛), where 𝑚 is the original message. has private key 𝑑 can see the message 𝑚. To find the
• 𝑐 can be decrypted using same (𝑛, 𝑗) by using 𝑑 as 𝑑, one has to do the prime factorization of 𝑛, which is
𝑐 𝑑 (𝑚𝑜𝑑 𝑛) = 𝑚 very difficult by the advanced computers.
Example
▪ Let A wants to send a message Modular Arithmetic Encipher the plaintext message ENDSIGHT using
in cryptography RSA with n = 8633 and j = 5
ENDSIGHT={069 078 068 083 073 071 072 084}
▪ The receiver B has to calculate 𝑛, 𝑗 and a private key
𝑑. To calculate 𝑛, 𝑗 695 (𝑚𝑜𝑑 8633) = 8005 similarly calculate the c
o Let us take any two prime numbers value for each number, then Cipher text c will be
c={8005 5646 6873 1302 3404 1415 3342 702}
𝑝1 = 53, 𝑝2 = 49
o 𝑛 = 𝑝1 𝑝2 = 3127
o 𝜙(𝑛) = (𝑝1 − 1)(𝑝2 − 1) = 3016

 Page 10
 Modular Arithmetic

The enciphertext 4611 4658 1493 has been

enciphered using RSA with n = 8051=83x97 and j =
5 . Decipher it
𝑛 = 8051 = 83 × 97
⇒ 𝜙(𝑛) = 82 × 96 = 7872
𝑘𝜙(𝑛) + 1
𝑑=
𝑗
Let us choose 𝑘 = 2 (choose any value so that 𝑑 will
be an integer), ⇒ 𝑑 = 3149
Given c={4611 4658 1493}
Using 𝑑 and 𝑐 𝑑 (𝑚𝑜𝑑 8051) we will get the message
m={67 65 82}
Message = “CAR”

RSA Encryption/Decryption Calculator

https://www.cs.drexel.edu/~jpopyack/Courses/CSP/Fa
17/notes/10.1_Cryptography/RSA_Express_EncryptD
ecrypt_v2.html

 Page 11