Number Theory CST 292 KTU Honors IV Semester - Dr Binu V P

The Extended Euclidean Algorithm is an essential algorithm in number theory. For given integers $a$ and $b$, the extended Euclidean algorithm not only calculate the greatest common divisor $d$ but also two additional integers $x$ and $y$ that satisfy the following equation. $$ax + by =d= gcd(a, b)$$ The existence of such integers is guaranteed by Bézout’s lemma.  Here’s how it works: Problem Statement: Given integers $a$ and $b$, find integers $x$ and $y$ such that $ax + by = gcd(a, b)$. Algorithm Steps: Start with the GCD of  $a$ and $b$. Reverse the steps in the Euclidean algorithm to find $x$ and $y$. Treat the numbers as variables and work our way backward to express the GCD as a linear combination of  $a$ and $b$ Example:  Given $a = 11$ and $b = 3$. We start with the GCD: $$11=3.3 + 2$$ $$3=1.2+1$$ $$2=2.1+0$$ So GCD=gcd(11,3)=1 Now we can reverse the process. Repeatedly replace terms until we get the final result.We have to consider the coefficient of  $a$ and $b$ as variable

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

  Linear Diophantine equations are equations of the form: $$ax+by=c$$ where $a, b, c, x,$ and $y$ are integers, and $a, b$ are not both zero. These equations are named after the ancient Greek mathematician Diophantus , who studied them extensively. The solutions to these equations are integers $x$ and $y$ that satisfy the equation. Linear Diophantine equations have applications in various fields, including number theory, cryptography, and optimization problems. A Diophantine equation is a polynomial equation with 2 or more integer unknowns. A Linear Diophantine equation (LDE) is an equation with 2 or more integer unknowns and the integer unknowns are each to at most degree of 1. Linear Diophantine equation in two variables takes the form of $𝑎𝑥+𝑏𝑦=𝑐$, where $𝑥,𝑦∈ℤ$ and $a, b, c$ are integer constants. $x$ and $y$ are unknown variables. A Homogeneous Linear Diophantine equation (HLDE) is $𝑎𝑥+𝑏𝑦=0$,$x,y∈Z$. Note that $x=0$ and $𝑦=0$is a solution, called the trivial solutio

Modular exponentiation is a fundamental operation in number theory and cryptography. It involves calculating the remainder when an integer, raised to a positive integer power, is divided by another positive integer, known as the modulus. Mathematically, if we have three integers $a$, $b$, and $m$, where $a$ is the base, $b$ is the exponent, and $m$ is the modulus, then modular exponentiation computes: $$a^b \pmod{m}$$ The straightforward approach to calculate this involves computing $a^b$ first and the finding the modulo $m$, which can become impractical for large numbers. However, by exploiting modular arithmetic properties, we can perform the calculation more efficiently. One common algorithm for modular exponentiation is the binary exponentiation method, also known as exponentiation by squaring. This algorithm reduces the number of multiplications required to compute the result. Here's how the binary exponentiation algorithm works: Start with the result $r$ initialized to 1. I

  Modular Division Modular division is a mathematical operation that involves dividing two integers under a specified modulus. It’s particularly useful in number theory, cryptography, and computer science. The goal is to find the remainder of the division (modulo) of one number by another. Definition Given three positive integers: $a, b$, and $m$, we want to compute $a/b$ under modulo $m$. In other words, we seek to find a number $c$ such that: $(b \cdot c) \mod m = a \mod m $ When Is Modular Division Defined? 1.Inverse Existence : Modular division is defined when the inverse of the divisor exists. The inverse of an integer $x$ is another integer $y$ such that $(x \cdot y) \mod m = 1$, where $m$ is the modulus. In other words, $x$ and $m$ must be co-prime (i.e., their greatest common divisor is 1). 2.Finding the Inverse : To compute modular division, we need to find the modular multiplicative inverse of $b$ under modulus $m$. If the inverse doesn’t exist (i.e., GCD(b, m) is not 1),

The least common multiple (LCM) of two or more numbers is the smallest number that is a multiple of each of the given numbers. In other words, it is the smallest number that is divisible by all the given numbers without leaving a remainder. If $a$ and $b$ are integers, then a common multiple of $a$ and $b$ is an integer $c$ such that $a|c$ and $b|c$.If  $a$ and $b$ are both non zero, then they have positive common multiples, so by the well ordering principle they have a least common multiple, or more precisely, a least positive common multiple.This is the unique positive integer $l$ satisfying 1)if $a|l$ and $b|l$ ( so $l$ is the common multiple) and  2)if $a|c$ and $b|c$ , with $c>0$ and $l \le c$ ( so no positive common multiple is less than $l$). we usually denote $l$ by $lcm(a,b)$. or simply $[a,b]$.For example $lcm(15,10)=30$, Since the positive multiples of 15 are 15,30,45,....while those of 10 are 10,20,30,40,.....The properties of least common multiples can be deduced from

  Fermat primes Numbers of the form $F_n= 2^{2^n}+1$ were studied by the outstanding French Mathematician Pierre de Fermat and are called Fermat Numbers. The first five Fermat Numbers are $F_0=3,F_1=5,F_2=17,F_3=257$ and $F_4=65537$ In order to find specific examples of primes, it seems reasonable to look at integers of the form $2^m \pm 1$, since many small primes such as $3,5,7,17,31\ldots$ have this form If $2^m+1$  is prime then $m=2^n$ for some integers $n \ge 0$ Proof: we prove the contra positive that $m$ is not a power of 2 then $2^m + 1$ is not prime.If $m$ is not a power of 2, then $m$ has the form $2^nq$  for some odd $q>1$.Now the polynomial $f(t)=t^q+1$ has a root $t=-1$.So it is divisible by $t+1$.This is a proper factor since $q >1$, so putting $t=x^{2^n}$ we see that the polynomial $g(x)=f(x^{2^n})=x^m+1$ has a proper factor $x^{2^n}+1$.taking $x=2$ we see that $2^{2^n} +1$ is a proper factor of the integer $g(2)=2^m +1$, which cannot therefore be prime.  Number