Euclidean Algorithm



One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.First, we need a simple definition: Two integers are relatively prime if their only common positive integer factor is 1.

Greatest Common Divisor
Recall that a  nonzero $b$ is defined to be a divisor of $a$  if $a=mb$ for some $m$, where $a , b,$  and $m$ are integers.We will use the notation $gcd(a , b)$ or $(a,b)$ to mean the greatest common divisor of $a$ and $b$. The greatest common divisor of $a$ and $b$  is the largest integer that divides both $a$ and $b$ .We also define $gcd(0, 0) = 0$.

More formally, the positive integer $c$ is said to be the greatest common divisor of $a$ and $b$ if
1.$c$ is a divisor of $a$ and $b$ .
2. Any divisor of $a$  and $b$ is a divisor of  $c$.

An equivalent definition is the following:
$gcd(a, b) = max[k, $such that $k | a$ and $k | b]$

Because we require that the greatest common divisor be positive,$gcd(a,b)=gcd(a-b)=gcd(-a,b)=gcd(-a,-b)$. In general $gcd(a,b)=gcd(|a|,|b|)$
Example:
$gcd(60,24)=gcd(60,-24)=12$

Also, because all nonzero integers divide 0, we have $gcd(a,0)=|a|$.

Two integers $a$ and $b$ are relatively prime if their only common positive integer factor is 1. This is equivalent to saying that $a$ and $b$ are relatively prime if $gcd(a, b) = 1$.


Finding the greatest common divisor

Lets describe the Euclids algorithm for finding the greatest common divisors of two integers.
Suppose we have integers $a, b$ such that $d = gcd(a, b)$. Assume $a \ge b \gt 0$. Now dividing $a$ by $b$ and applying the division algorithm, we can state

$$a=q_1b+r_1 \quad 0 \le r_1 \lt b$$

If it happens that $r_1=0$, then $b|a$  and $d=gcd(a,b)=b$. But if  $r_1 \ne 0$, we can state that $d|r_1$. This is due to the basic properties of divisibility: the relations $d|a$ and $d|b$ together imply that $d|(a-q_1b)$, which is the same as $d|r_1$. Before proceeding with the Euclidian algorithm, we need to answer the question:What is the $gcd(b,r_1)$? We know that $d|b$ and $d|r_1$ . Now take any arbitrary integer $c$ that divides both $b$ and $r_1$ . Therefore, $c|(q_1b+r_1)=a$ . Because $c$ divides both $a$ and $b$ , we must have $c \le d$ , which is the greatest common divisor of $a$ and $b$.Therefore $d=gcd(b,r_1)$.

Lets now assume that $r_1 \ne 0$. Because $b \gt r_1$, we can divide $b$ by $r_1$and apply the division algorithm to obtain:
     $$b=q_2r_1 + r_2 \quad 0 \le r_2 \lt r_1$$



We can define the Euclidean algorithm concisely as the following recursive function.( where % is the mod operator)
Euclid(a,b)
if (b=0) then 
        return a;
else 
        return Euclid(b, a % b);

Example:
gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11
gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6
gcd(11, 10) = gcd(10, 1) = gcd(1, 0) = 1


Time Complexity: O(log(min(a, b))) since the algorithm reduces the values quickly by taking the modulus.

Python Code:
def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Example usage:
a = 48
b = 18
gcd = euclidean_gcd(a, b)
print("GCD of", a, "and", b, "is:", gcd)

We can also use built in function gcd() from math module
Example:
import math
print(math.gcd(10,100))

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