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

  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 sol...

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 ...

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 ded...

  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 ther...

  Definition: An integer $p\gt 1$ is said to be prime if the only positive divisors of $p$ are 1 and $p$ itself. Note that 1 is not prime.The smallest prime is 2 ( even) and all other primes (such as 3,5,7,11...) are odd.An integer $n \gt 1$ which is not prime (such as 4,6,8,9....) is said to be composite; such an integer has the form $n=ab$, where $1 <a < n$ and $1 <b < n$ Let $p$ be a prime and $a$ and $b$ are any integers. Then 1)either $p|a$ or $p$ and $a$ are coprime. Proof: by definition $gcd(a,p)$ is a positive divisor of $p$, so it must be 1 or $p$ since $p$ is prime.If $gcd(a,p)=p$, then since $gcd(a,p)$ divides $a$ we have $p|a$; if $gcd(a,p)=1$, then $a$ and $p$ are coprime. Example: $gcd(15,5)=5,$ so $5|15$ $gcd(7,5)=1$, so 7,5 are coprime 2)if $p|ab$, then $p|a$ or $p|b$ Proof:Let $p|ab$. If $p$ does not divide $a$ then $gcd(a,p)=1$.Now using Bezout's identity $1=ax+py$, for some $x$ and $y$, so $b=axb+pyb$.Based on our assumption $p|ab$ it is clear th...

Fermat's Factorization Method is a mathematical algorithm devised by Pierre de Fermat, a French mathematician from the 17th century. It's a technique used to factorize composite numbers into their prime factors. Fermat's factorization method ,  is based on the representation of an odd integer as the difference of two squares: � = � 2 − � 2 . That difference is algebraically factorable as  ( � + � ) ( � − � ) ; if neither factor equals one, it is a proper factorization of  N . Each odd number has such a representation. Indeed, if  � = � �  is a factorization of  N , then � = ( � + � 2 ) 2 − ( � − � 2 ) 2 Since  N  is odd, then  c  and  d  are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let  c  and  d  be even.) In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combinati...