Introduction : Prime Numbers Flashcards
(Bézout’s Lemma)
Suppose the hcf(m , n) = d. Then there exists s,t c Z such that sm + tn = d
(Factorization Algorithm)
To factorise N:
- Start with n =N and p=2
- If p divides n then record the prime factor p, replace n with n/p and repeat this step.
- If p does not divide n, replace p with the next smallest prime.
- If P <= n^1/2 then return to step 2.
- If P > n ^1/2 then record the prime factor n, and end.
(The Sieve of Eratosthenes)
Step 1
Cross out 1 We have agreed that 1 is not a prime.
Step 2
Find the next unmarked number, p, and circle it.
Step 3 Cross out all proper multiples of p which are not yet crossed out.
Step 4
If there remain unmarked entries in the grid, return to Step 2.
Step 5
If there are no unmarked entries then end.
Prove there are infinitely many prime numbers
Suppose that we have a finite set of primes p1 , p2, … pt . Let N be the product p1 …. pt of all these primes. Now if we try to divide N + 1 by any if the primes in our set, we get remained 1 ; so none of these primes can divide N + 1. but N + 1 /= 1, and so N + 1 must have a prime divisor ; hence our finite set of primes does not contain all primes.
(The Prime Number Theorem)
x ( n ) ~ n
——–
log n
fermats little theorem
let p be prime, and let a be that a^p = a mod p. If P is prime and a is coprime with p, then a^p-1 = 1 mod p
Which algorithm calculates highest common factor?
Euclidian Algorithm
fundamental theorem of arithmetic
Let n c N, then n has a unique factorisation as a product of primes.
Prime factorisation
reduce into powers of primes
e.g 2024 = 2^3 x 11 x 23
Find the period of 15 in Z17.
8
Tutorial 1
calculate 7^10000 in Z103
32
Tutorial 1
Find x ∈ N such that 13x ≡ 666 (mod 1000).
Euclids
x = 282
SS1
