Prime Numbers and Prime-Power Factorizations

 

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 that $p|b$,ie; $p|a$ or $p|b$

Note: if $p$ is prime and $p$ divides $a_1,a_2,\ldots,a_k$, then $p$ divides $a_i$ for some $i$.
Example:
$5|3.5$ implies that $5|5$
$3|7.3$ implies that $3|3$

Fundamental Theorem of Arithmetic

This asserts that every integer $n >1$ can be written in an essentially unique way, as a product of prime powers. This allows many number theoretic problems to be reduced to questions about prime numbers.

Theorem:
every integer $n >1$  has  a prime power factorization
$$n=p_1^{e_1}p_2^{e_2} \ldots p_k^{e_k}$$
where $p_1,p_2,\ldots, p_k$ are distinct primes and $e_1,e_2,\ldots,e_k$ are positive integers; this factorization is unique, apart from the permutation of factors.

Example: 200 has the prime power factorization $2^3.5^2$, or alternatively $5^2.2^3$ if we permute the factors.But it has no other prime-power factorization.

Suppose that integers $a$ and $b$ have factorizations

$$a=p_1^{e_1}\ldots p_k^{e_k} \:\text{and}\: b=p_1^{f_1}\ldots p_k^{f_k}$$

where we have $e_i,f_i >=0$ to allow for the possibility that some primes $p_i$ may divide one but not both of $a$ and $b$. Then we have

$$ab=p_1^{e_1+f_1}\ldots p_k^{e_k+f_k}$$
$$a/b=p_1^{e_1-f_1}\ldots p_k^{e_k-f_k}\quad \text{if} b|a$$
$$a^m=p_1^{me_1}\ldots p_k^{me_k}$$
$$gcd(a,b)=p_1^{min(e_1,f_1)}\ldots p_k^{min(e_k,f_k)}$$
$$lcm(a,b)=p_1^{max(e_1,f_1)}\ldots p_k^{max(e_k,f_k)}$$

Example:Product
Let's find the product of 15 and 24

$15=3^1 \cdot 5^1$
$24=2^3 \cdot 3^1$
$15 \times 24 = 2^3 \cdot 3^{1+1} \cdot 5^1$
$360=8 \cdot 9 \cdot 5$

Example:Division
lets find the division of 28 by 14
$28=2^2 \cdot 7$
$14=2 \cdot 7$

$28/14=2^{2-1} \cdot 7^{1-1}$
$28/14=2$

Example: Exponentiation
Lets find $15^3$

$15=3^1 \cdot 5^1$
$15^3 = 3^3 \cdot 5^3 $
$15^3=27 \cdot 125 $
$15^3=3375$

Example:GCD

Lets find the gcd(72,15)

$72=2^3 \cdot 3^2$
$15=3^1 \cdot 5^1$
$gcd(72,15)=2^0 \cdot 3^1 \cdot 5^0$
$gcd(72,15)=3$


Example:LCM
Lets find the lcm(72,15)
$72=2^3 \cdot 3^2$
$15=3^1 \cdot 5^1$

$lcm(72,15)=2^3 \cdot 3^2 \cdot 5^1$
$lcm(72,15)=8 \cdot 9 \cdot 5=360$




Distribution of Primes
Euclid's theorem, that there are infinitely many primes, is one of the oldest and  most attractive in mathematics.

Theorem: There are infinitely many primes

Proof: The proof is by contradiction; we assume that there are only finitely many primes, and then we obtain a contradiction from this, so it follows that there must be infinetly many primes.
Suppose that the only primes are $p_1,p_2,\ldots, p_k$.Let

$$m=p_1.p_2 \ldots p_k+1$$

Since $m$ is an integer greater than 1.the fundamental theorem of arithmetic implies that it is divisible by some prime $p$.( this includes the possibility that $m=p$).By our assumption , this $p$ must be one of the primes in $p_1,p_2,\ldots p_k$, so $p$ divides their product $p_1,p_2,\ldots . p_k$. Since $p$ divides both $m$ and $p_1.p_2 \ldots , p_k$, it divides $m-p_1.p_2.\ldots.p_k=1$, which is impossible. We deduce that our initial assumption was false, so there must be infinitely many primes.

Prime Number Theorem

The prime number theorem (PNT) describes the asymptotic distribution of prime numbers among the positive integers. It quantifies the intuitive idea that primes become less common as they become larger. Here are the key points about the prime number theorem:


Statement:
The prime number theorem states that for large values of $x$, the prime-counting function $\pi(x)$(which counts the number of primes less than or equal to $x$) is approximately equal to $\frac{x}{\ln(x)}$
In other words, as $x$ increases, the probability that a randomly chosen integer not greater than $x$ is prime approaches $\frac{1}{\ln(x)}$

The prime number theorem asserts that: $ \lim_{{x \to \infty}} \frac{\pi(x)}{\frac{x}{\ln(x)}} = 1 $

This means that $\frac{x}{\ln(x)}$ is a good approximation for $\pi(x)$ in terms of the asymptotic distribution of prime numbers.

Note:
There are infinitely many primes of the form $4q+3$
If $a$ and $b$ are coprime, then there are infinitely many primes of the form $aq+b$

Python Code
primality checking 
from sympy.ntheory.primetest import isprime
print(isprime(15))
False
print(isprime(11))
True
generate primes in a range [a,b)
from sympy.ntheory.generate import primerange
for i in primerange(1,50):
    print(i,end=" ")
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
primes less than a given number
from sympy.ntheory.generate import primepi
print(primepi(50))
15
return the n'th prime
from sympy.ntheory  import prime
print(prime(5))
11

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