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

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

  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 combination of trial division and Fermat's is more effective than either by itself. Basic method O

 Two practical problems that arise in Number Theory related to Primes are 1) How do we determine whether the given integer $n$ is prime ( primality testing) 2)How do we find the prime power factorisation of a given integer $n$. Primality Testing An integer $n>1$ is composite if and only if it is divisible by some prime $p \le \sqrt{n}$ Proof:If $n$ is divisible by such a prime $p$, then since $1 \lt p \le \sqrt{n} \lt n$, it follows that $n$ is composite. Conversely if $n$ is composite then $n=ab$ ,where $1 \lt a \lt n$ and $1 \lt b \lt n$; at least one of $a$ and $b$ is less than or equal to $\sqrt{n}$ ( if not $ab > n$), and this factor will be divisible by a prime $p \le \sqrt{n}$, which then divides $n$. Example: we can check 97 is prime by checking that it is divisible by none of the primes $p \le \sqrt{97}$, namely 2,3,5 and 7. This method requires us to test, whether an integer is divisible by various primes $p$.For certain small primes $p$ there are simple ways of doin