Prime factorization arrange the primes that and exponentsi

1 Factorisation of Integers

Definition α ∈R then ⌊α⌋is the greatest integer which is less than or equal to α.
Ex ⌊3⌋= 3,	√2

Then ⌊α⌋⩽α < ⌊α⌋+ 1

Proposition 1 If a and b are two integers with b > 0 then there are integers q and r

a		0		a	<	1
		0		b a	<	1
		0		b a	<
		0		b
	then a = qb + r with q =		a b	.
b	then a = qb + r with q =		a b	.

Proposition 2 If b ̸= 0, c ̸= 0 then

(a)

Definition If b|a and b ̸= 1 or a then we say b is a proper divisor of a. If b does not divide a write b ∤a.

Definition P = {p ∈N : p > 1 and the only divisors of p are 1 and p} are the prime numbers. Then N \ (P ∪{1}) are the composite numbers.
P = {2, 3, 5, 7, 11, 13, 17, 19, 23, . . .}.

This process must terminate in less than n steps. Hence n = q1q2 . . . qs with s < n. □

Ex 10725 = 3 · 5 · 5 · 11 · 13

αj

We can use the sieve of Eratosthenes to list the primes 2 ⩽p ⩽N.

If n ⩽N and n is not prime, then n must be divisible by a prime p ⩽and p2 >√N ⇒p1p2 > N).	√N (if p1 >	√	N

(ii) 9, 15, 21, 27, . . . multiples of 3 from 32on

(iii) 25, 35, 55, 65, . . . multiples of 5 from 52on

Ex N = 16,

{2, 3, ̸4, 5, ̸6, 7, ̸8, ̸9, ̸10, 11, ̸12, 13, ̸14, ̸15, ̸16}

√N. We are left with all

How many primes are there ?

Note:

n=1

∞

π2

n=1

We can show	∞	1	=
	j=1	pj	= ∞

If x > 0, let S(x) = #{n ∈N : n2⩽x}. Then S(x) = ⌊√x⌋. We can show
π(x)	=
π(x)
	∼

{0}. If a ∈Z then M = {na : n ∈Z} is a modulus.

Proposition 4 If M is a modulus with a, b ∈M and m, n ∈Z then ma + nb ∈M.

Proof. Let d be the least positive integer in M with 0 < d.

Claim: every element of M is a multiple of d. If not (???) let n ∈M have d ∤n. Then

(i)

(ii)

Algorithm. From Proposition 5: (a = 323, b = 221)

323	=	221 · 1 + 102 102 · 2 + 17 17 · 6 + 0
221	=
102	=

17	=
	=
	=

Proposition 7 If p ∈P and p|ab then p|a or p|b.

Proposition 8 If c > 0 and (a, b) = d then (ac, bc) = dc.

Proof. ∃x, y ∈Z so	xa + yb		=	d
⇒dc = (ac, bc). (ac, bc) \| dc. Also d \| a□			=
⇒dc = (ac, bc). (ac, bc) \| dc. Also d \| a□	⇒	cd \| ca (and similarly cd \| cb) ⇒

a number n ∈N is unique.

Proof.

p1 < p2 < · · · < pk and q1 < q2 < · · · < qk, pℓ= qℓfor 1 ⩽ℓ⩽k. If β1 < α1, divide n by pβ1 1to get pα1−β1 pα2 2· · · = pβ2 2· · · ⇒α1= β1etc. □

a =

and	b =	m	βj p j

j=1

with αj ⩾0, βj ⩾0 then	(a, b) =	m

Ex	a	=
	b	=	213051
	⇒(a, b)	=	213051

Proposition 11	{a, b} =	j=1	max (αj, βj) p j
Proposition 11

	m	max (αj, βj)+min (αj, βj) p j	.
LHS =	m	max (αj, βj)+min (αj, βj) p j	.

						m
LHS =	j=1		=	j=1	αj p j·	j=1

□

Alternative Characterisation of the GCD

to sign.

Proof. If g1 and g2 satisfy this property, then g1 and g2 are both common divisors with

= {±1, ±2, ±3, ±4, ±6, ±12} = D12 {±1, ±2, ±3, ±6, ±9, ±18} = D18
common divisors = {±1, ±2, ±3, ±6} = D12 ∩D18

So ±6 satisfies the property. Hence, fixing the sign, 6 = (12, 18).

Proposition 13 x, y ⇔(a, b)\|n.

(⇒) By Proposition 6 (ii), (a, b)|ax + by = n. □

Proposition 14 Let (a, b) = 1 and let x0, y0 be a solution to ax + by = n (a solution

x	=
y	=

= n

so each such x and y is a solution. If ax0 + by0 = n and ax + by = n also, then

Proof. By Proposition 14,

x	=	x0 + bt
y	=	x0 + bt
y	=

⇒(x0 + bt) > −1
⇒(x0 + bt) ⩾ 0.

Hence n is representable. Finally suppose ax + by = ab −a −b (???) x ⩾0, y ⩾0.

σ(n)	=
σ(n)	=

d|n

Ex σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28

n =	1 ⩽d < n d \| n	d

Proposition 15 If n =m j=1p	αj
Proposition 15 If n =m j=1p	j
σ(n) =				m		pj −1
σ(n) =				j=1		pj −1
Proof. All divisors of n have the form d = px1 1· · · pxm mwith 0 ⩽xj⩽αj. Hence
α1				αm
σ(n)	=	x1=0	· · ·		xm=0
α1
=		x1=0					· · ·	pxm m
=		RHS above.

Proof. This follows from Proposition 15. □ Theorem 5
σ(m)	=
	=
	=
=		2m

so m is perfect. Let a be an even perfect number. a = 2n−1u, u > 1, 2 ∤u. (Note that

since a is perfect. Hence	σ(u) =

But u\|u and□	2n−1\|u so u has just two divisors hence u ∈P and	2n−1= 1 ⇒u = 2n −1.

If a = 2 and n = jℓ, where j is a proper divisor of n, then 2n−1 = (2j)ℓ−1 is divisible by 2j−1 (a = 2jin the equation above). Hence n ∈P. □
web: http://www.utm.edu/research/primes/mersenne.shtml
Theorem 7 If 2m+ 1 ∈P then m = 2n.

Proof. If m = qr, where q is odd, then
2qr+1 = (2r)q+1 = (2r+1)(2r(q−1)−2r(q−2)+· · ·+1) and 1 < 2r+1 < 2qr+1 so 2qr+1 cannot be prime. Hence m has no odd prime factor. Hence m = 2n, n ∈N. □Note The factorization
an−bn= (a −b)(an−1+ an−2b + an−3b2+ · · · + bn−1)

an+ 1	=
	=
	=

Definition The nth Fermat number, Fn = 22n+ 1

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.

Proof. Let

a	=	27
b	=
	=
	=

Therefore

and 1 + ab = 641.	□	225+ 1	=	(28)4+ 1
			=
			=
			=
			=
			=
			=

	n	+	n	+	n	+
	p	+	p2	+	p3	+ · · ·

Thre re	n	n!	=
Thre re	n	multpl fp	n
Thre re	p	multpl fp	p2	ulipesfp,tc

Each multiple of p contributes 1 to α. Each multiple of p2has already contributed 1,

n						+	n
p						+	p2	+
etc. Hence	α=	n	+	n	+		n	+
etc. Hence	α=	p	+	p2	+		p3	· · · +
where r is the first N such that pr+1> n. So							n	= 0 ∀β ⩾r + 1.
where r is the first N such that pr+1> n. So							pβ	= 0 ∀β ⩾r + 1.

				12		12
12!	=	α		3	+	9	+
		=	4 + 1 + 0
		=	5.

Definition a ≡b (mod m) if m|a −b, m ̸= 0, a, b, m ∈Z. If so we say a is congruent to b modulo m. We call m the modulus.

Proposition 17 ≡is an equivalence relation on Z and the set of equivalence classes

a1	≡ ≡	b1	(mod m)	⇒	a2 + a2 a1 · a2	≡ ≡	b1 · b2 b1 + b2	(mod m)
a1		b1	(mod m)					(mod m)
a2		b2	(mod m)					(mod m)

		⇒a ≡b
	(mod m)	⇒a ≡b