Primes

Prime

A number

p \in ℕ_{2}

is said to be prime if it's only divisors are

1

and

p

symbolically that is

\forall d \in ℕ_{1}, (d | p) ⟹ d \in {1, p}

Set of Primes

We denote the set of primes as

ℙ

If a Prime Divides Another they are Equal

Suppose that

p, q \in ℙ

, then

p | q ⟹ p = q

Since

p | q

then we know that

p = 1

p = q

the former is impossible since

ℙ \subseteq ℕ_{2}

therefore

p = q

as needed.

Primes of the Form 4k Plus Something

Suppose that

p \in ℙ_{3}

then there exists some

k \in ℕ_{0}

such that

p = 4 k + 1 or p = 4 k + 3

By the quotient remainder theorem we have that

p = 4 q + r

where

q \in ℤ

and

r \in [0, \dots, q - 1]

, when

p = 3

the only possibility is that

q = 0

and

r = 3

, on the other hand for any

p \geq 5

we have that

q \geq 1

, now if

q = 0

r = 2

then the prime is divisible by

2

and which makes

p

not prime, which is a contradiction, therefore

r \in {1, 3}

Increasing Prime Function

We let the function

p_{i} : ℕ_{1} \to ℙ

be an increasing function such that

p_{1} = 2

and there are no primes between

p_{i}

and

p_{i + 1}

This function looks like $2, 3, 5, 7, 11, 13, 17, \dots$

Composite

We say that

n \in ℤ

where

| n | \geq 2

is composite if there exists an

x \in {2, \dots, n - 1}

such that

x | n

The composites union the primes is $ℤ ∖ {- 1, 0, 1}$

Composite iff Not Prime

Let

a \in ℕ_{1}

then

a

is composite iff

a

is not prime

We know that it's always true that

a | a

and

1 | a

therefore if

a

is not prime iff it has some other divisor other than

1

a

iff

a

is composite

A Prime is Relatively Prime to Anything Else That is Not a Multiple of It

Suppose that

p

is prime and

n \in ℤ

then

p ∤ n

iff

\gcd (p, n) = 1

$⟹$ Since $p$ is prime, then its only divisors are $1$ and itself. We assume that $p$ does not divide $n$ therefore that's the same as saying that $n$ is not a multiple of $p$ . Now if we consider $\gcd (p, n)$ then its subset of the divisors of $p$ so the gcd could only $p$ or $1$ , if it were $p$ that would imply that $p | n$ but that's a contradiction, therefore the gcd is $1$ .

Suppose that $\gcd (p, n) = 1$ and for the sake of contradiction that $p | n$ that means there is a $k \in ℕ$ such that $n = k p$ in that case we have $\gcd (p, n) = \gcd (p, k p)$ therefore $\gcd (p, k p) \geq p$ which is a contradiction because any prime is greater than one.

A Prime Divisor of a Product Divides at Least One

p, a, b \in ℤ

and we know

p

is prime and

p | a b

then

p | a

p | b

p

were to divide

a

, the proof is over so we assume that it does not. therefore

\gcd (p, a) = 1

and then

1 = a s + p t

, then

b = (a b) s + p t b = (k \cdot p) s + p t b

, so then

p

divides the right hand side, therefore

p | b

, as needed.

Every Number is Divisible by a Prime

For any

n \in ℕ_{2}

there is a prime

p

such that

p | n

To show existance we will use the well ordering principle so consider the set $S : = {c \in ℕ_{2} : c | n}$ observe that $n \in S$ so therefore $S \neq \emptyset$ and therefore by the well ordering principle it has a least element $p \in S$ therefore by the definition of $S$ we know that $p | n$ , lets show that $p$ is prime.

Let $d \in ℕ_{1}, d | p$ if $d = 1$ , then $d \in {1, p}$ so all is well, on the other hand if $d > 1$ so that $d \in ℕ_{2}$ then since we already knew that $p | n$ and that division is transitive then we know that $d | n$ which means that $d \in S$ , since $p$ is the minimal element of $S$ then $p \leq d$ at the same time since $d | p$ then we know that $d \leq p$ , thus since $\leq$ is anti-symmetric, then $d = p$ .

Thus $p$ is prime, and $p | n$ as needed.

Every Number is a Product of Primes

For every

n \in ℕ_{2}

n : = p_{1} \cdot p_{2} \cdot \dots \cdot p_{k}

for some

k \in ℕ_{1}

We prove the statement true via strong induction, for the base case of $n = 2$ we see that $p_{1} = 2$ works, namely that $2 = 2$ .

Now suppose for some $j \in ℕ_{2}$ the statement we'd like to prove holds for ${2, \dots, j}$ we'll prove that the statement holds true for $j + 1$ , so consider $j + 1$ , if it is prime, then we are done, as we can take it as the singleton product, elsewise it is not prime, and therefore it is composite so we get $a, b \in ℕ_{2}$ such that $a b = j + 1$ by our induction hypothesis we know that the statement holds true for $a, b$ and thus we get $a = p_{1} \cdot \dots \cdot p_{n}$ and $b = q_{1} \cdot \dots \cdot q_{m}$ for some $m, n \in ℕ_{1}$ , thus $j + 1 = p_{1} \dots p_{n} q_{1} \dots q_{m}$ so that $j + 1$ is the product of $m + n$ primes as needed.

There are Infinitely Many Primes

As per title.

Suppose that there were finitely many primes, and we listed all of them here:

p_{1}, \dots p_{k}

for

k \in ℕ_{1}

and consider

M : = p_{1} \dots p_{k} + 1

For every

i \in [1, k]

we have that

M % p_{i} = 1

therefore

p_{i} ∤ P

, at the same time

M

must be divisible by some prime

p^{'}

but clearly

p^{'} \neq p_{i}

for any

i \in [1, k]

or else

M % p_{i} = 0

which would be a contradiction, since it's not equal to any of the primes we listed, this is a contradiction because we know that it contained all primes, therefore our assumption is incorrect and there must be infinitely many primes.

There is a Prime Between n and n Factorial

For any

n \in ℕ_{3}

there is a prime number

p

such that

n < p < n!

Let

N = {p \in ℙ : p \leq n}

since

n \geq 3

then at least

2, 3 \in N

so it is non-empty. Since

n! \geq 6

then we know that

n! - 1 \in ℕ_{2}

and therefore there is a prime number which divides it, say it is

q

, for any

p \in N

we know that

n! - 1 \equiv - 1 (\mod p)

therefore

q \notin N

thus

q > n

, since

q | n! - 1

then

q \leq n! - 1 < n!

so that

n < q < n!

n Minus 1 Factorial is Divisible by n

Let

n \in ℕ_{4}

, show that if

n

is not a prime then we have

(n - 1)! \equiv {\begin{matrix} 2 (\mod n) & a m p; if n = 4, \\ 0 (\mod n) & a m p; if n \geq 5 \end{matrix}

In the case that $n = 4$ then we know that $(n - 1)! = 6$ which has remainder 2 upon division by $4$ as needed.

On the other hand, whenever we have $n \geq 5$ then since $n$ is not prime, then it is composite and therefore there exists $a, b \in [2, \dots, n - 1]$ such that $n = a b$ . If $a \neq b$ then $(n - 1)! = (n - 1) \dots a \dots b \dots 2 \cdot 1$ therefore $n = a b | (n - 1)!$ so that $(n - 1)! \equiv 0 (\mod n)$ .

On the other hand, supposing that $a = b$ then we see that $n = a^{2}$ since $a \geq 2$ then we know that $a^{2} \geq 2 a$ . Actually we know more, since $n \geq 5$ then $a > 2$ so we can say that $a^{2} > 2 a$ so that $n > 2 a$ so that $a, 2 a$ both appear in the factorials product so that $a^{2} | (n - 1)!$ as needed.

There are Gaps of Arbitrary Size between Consecutive Primes

Suppose that

(p_{1}, p_{2}, p_{2}, \dots)

is an increasing sequence of all the primes, then for every

m \in ℕ_{1}

there exists an

N \in ℕ_{1}

such that

p_{N + 1} - p_{N} \geq m

Let

m \in ℕ_{1}

, consider the following numbers

(m + 1)! + 2, (m + 1)! + 3, \dots, (m + 1)! + (m + 1)

since there are

(m + 1) - 2 + 1 = m

numbers here, and for each element of the form

(m + 1)! + i

we know that

i | (m + 1)! + i

since

i \in ℕ_{2}

this makes it composite, and thus not prime, thus take

N

as the greatest index such that

p_{N} < (m + 1)! + 2

thus the gap between

p_{N}

and

p_{N + 1}

must be at least

m

as needed.

Fundamental Theorem of Algebra

For every

n \in ℕ_{2}

can be written uniquely as

n = \prod_{i \in ℕ_{1}} p_{i}^{α_{i}}

α_{i} \in ℕ_{1}

where all but finitely many

α_{i} = 0

Prime Factors

Let

n \in ℕ_{2}

and consider its prime factorization

n = \prod_{i \in ℕ_{1}} p_{i}^{α_{i}}

α_{i} \in ℕ_{1}

where all but finitely many

α_{i} = 0

then we define

pf (n) = {p_{i} : α_{i} \geq 1}

Prime Power Sequence

Given any

n \in ℕ_{1}

and its prime factorization

\prod_{i \in ℕ_{1}} p_{i}^{a_{i}}

then we define

pps (n) : = (a_{1}, a_{2}, a_{3}, \dots)

Note that

pps : ℕ_{2} \to {(x_{n}) : ℕ_{1} \to ℕ_{0}}

Note that since each number has a unique factorization then $pps$ is a bijection, and so ${pps}^{- 1}$ exists.

Products as the Addition of Power Sequences

Suppose that

a, b \in ℕ_{2}

then

pps (a b) = pps (a) + pps (b)

Relatively Prime In terms of Prime Factorization

The following are equivalent

$\gcd (a, b) = 1$
$\max (pps (a), pps (b)) = 0$
$pf (a) \cap pf (b) = \emptyset$

Coprime and 5

Suppose that

a, b \in ℤ

are coprime, then find all possible values of

\gcd (a + b, 5 a b)

If $p | a$ then we know that $p | b$ but then $\gcd (a, b) \neq 1$ which would be a contradiction, therefore $p ∤ a$ , but symmetrically $p ∤ b$ therefore we must have that $p | 5$ therefore $p = 5$

The above says that given any prime divisor of $d$ then it turns out that prime divisor must be $5$ therefore $d = 5^{k}$ for some $k \in ℕ_{1}$ . Suppose that $k \geq 2$ , if that's true then we have $5^{k} | 5 a b$ and $5^{k} | a + b$ from the former so we have $5^{k - 1} | a b$ therefore $5^{k - 1} | a$ or $5^{k - 1} | b$ , without loss of generality if we assume that $5^{k - 1} | a$ then in conjunction with $5^{k} | a + b$ we have $j 5^{k} = a + b = 5^{k - 1} l + b$ therefore $b = 5^{k - 1} (j 5 - l)$ so that $5^{k - 1} | b$ therefore $\gcd (a, b) \geq 5^{k - 1}$ which is a contradiction, therefore it must be that $k = 1$ .

Therefore the only possible values of $d$ is $1$ or $5$ therefore the only possible values of $\gcd (a + b, 5 a b)$ is $1$ or $5$

Subsequence of the sum of Two Disjoint Power Sequences Is Still a Disjoint Sum

Suppose that

\max (pps (a), pps (b)) = 0

and that

(x_{n}) \leq pps (a) + pps (b)

then

(x_{n}) = (a_{n}) + (b_{n})

where

(a_{n}) \leq pps (a)

and

(b_{n}) \leq pps (b)

and

\max ((a_{n}), (b_{n})) = 0

A Number Divides a Coprime Product iff It is the product of Individual Divisors

Suppose that

\gcd (a, b) = 1

then

c | a b

if and only if

c = d_{a} d_{b}

where

d_{a}, d_{b}

are divisors of

a, b

respectively

$⟹$ Suppose that $c | a b$ therefore $pps (c) \leq pps (a b) = pps (a) + pps (b)$ and therefore $pps (c) = (a_{n}) + (b_{n})$ where $(a_{n}) \leq pps (a)$ and $(b_{n}) \leq pps (b)$ where $\max ((a_{n}), (b_{n})) = 0$ (by the corollary). Therefore $c = {pps}^{- 1} (a_{n}) {pps}^{- 1} (b_{n})$ but we know that ${pps}^{- 1} (a_{n}) | a$ and ${pps}^{- 1} (b_{n}) | b$ as needed.

$⟸$ Suppose that $c = d_{a} d_{b}$ , since they are divisors we know that there exist $k_{a}, k_{b} \in ℤ$ such that $a = k_{a} d_{a}$ and $b = k_{b} d_{b}$ so then $a b = k_{a} k_{b} d_{a} d_{b} = k_{a} k_{b} c$ therefore $c | a b$ as needed.

Euclid

For any

a, b, p \in ℕ_{1}

then if

p

is prime, we have

p | a b ⟹ ((p | a) \lor (p | b))

If a Prime Divides a Product it Divides at Least One of the Factors

Suppose that

a_{1}, \dots a_{n} \in ℕ_{1}

and

p | \prod_{i = 1}^{n} a_{i}

then there exists a

k \in [1, \dots, n]

such that

p | a_{k}

Prime Divisors of a Factorial are Bounded by the Argument

For every

p \in ℙ

and

n \in ℕ_{2}

such that

p | n!

then

p \leq n

Since

p | 1 \dots n

then there exists some

k \in [1, \dots, n]

such that

p | k

therefore

p \leq k \leq n

so that

p \leq n

A Divisor of a Product of Primes is a Product of Primes with Smaller Powers

Suppose that dm

GCD and LCM as Prime Powers

Suppose that

P = {p_{1}, \dots p_{k}}

is a collection of primes such that

a = \prod_{p_{i} \in P} p_{i}^{α_{i}} and b = \prod_{p_{i} \in P} p_{i}^{β_{i}}

where

α_{i}, β_{i} \in ℕ_{0}

, then

\gcd (a, b) = \prod_{p_{i} \in P} p_{i}^{\min (α_{i}, β_{i})} and lcm (a, b) = \prod_{p_{i} \in P} p_{i}^{\max (α_{i}, β_{i})}

Perfect Square iff Every Power in the Prime Factorization is Even

Let

n \in ℕ_{1}

then

n

is a perfect square if and only if

n = \prod_{i \in ℕ_{1}} p_{i}^{2 α_{i}}

$⟹$ Suppose that $n$ is a perfect square therefore $n = m^{2}$ for some $m \in ℤ$ but we know that $m = \prod_{i \in ℕ_{1}} p_{i}^{β_{i}}$ therefore $n = {(\prod_{i \in ℕ_{1}} p_{i}^{β_{i}})}^{2} = \prod_{i \in ℕ_{1}} p_{i}^{2 β_{2}}$

$⟸$ We have that $n = \prod_{i \in ℕ_{1}} p_{i}^{2 α_{i}} = {(\prod_{i \in ℕ_{1}} p_{i}^{α_{i}})}^{2}$ therefore $n$ is a perfect square.

Division and Prime Power Equivalence

Suppose that

a, d \in ℕ_{2}

then

d | a ⟺ pps (d) \leq pps (a)

Every Composite Three Digit Number must have a Prime Factor Less than or Equal to 31

As per title.

Assume that for the sake of contradiction the statement was not true, therefore there is a three digit number such that all of its prime factors are greater than 31, the next prime is

37

and so the smallest three digit number hvaing all prime factors greater than

31

would be

37^{2} = 1369

which is a four digit number, thus our assumption was false, so that every three digit number must have a prime factor less than or equal to

31

Lower Bound on Primes in Factorization Limits the Number of Prime Factors

Let

n \in ℕ_{2}

and suppose that

p ∤ n

for all primes

p \leq \sqrt[3]{n}

, what can we conclude about the prime factorizatio of

n

Suppose that

n = \prod_{i = 1}^{k} p_{i}^{α_{i}}

, we can see that

p_{i} | n

and therefore by the contrapositive of our assumption we have that

p_{i} \geq \sqrt[3]{n}

therefore

k \leq 2

for if

k \geq 3

then

\begin{matrix} n & a m p; = \prod_{i = 1}^{k} p_{i}^{α_{i}} \\ a m p; \geq \prod_{i = 1}^{k} p_{i} \\ a m p; \geq \prod_{i = 1}^{3} p_{i} \\ a m p; > \sqrt[3]{n} \sqrt[3]{n} \sqrt[3]{n} \\ a m p; = n \end{matrix}

so we've shown that

n > n

which is a contradiction so indeed

k \leq 2

, therefore we conclude that the prime factorization of

n

has at most two different primes in it.

Goldbach Equivalence

Show that every even integer

> 2

is the sum of two primes if and only if every integer

> 5

is the sum of three primes

$⟹$ Suppose the former, let $n \in ℕ_{1}$ such that $n > 5$ if $n$ is even, then so is $n - 2$ and we see $n - 2 > 2$ and so $n - 2 = p_{1} + p_{2} ⟺ n = p_{1} + p_{2} + 2$ , otherwise use $3$ .

$⟸$ Suppose the latter and let $n > 2$ be even, in other words $n \geq 4 > 3$ therefore $n + 2$ is an even number and we know that $n + 2 > 5$ therefore $n + 2 = p_{1} + p_{2} + p_{3}$ , since $n + 2$ is even then so is $p_{1} + p_{2} + p_{3}$ but the sum of three numbers is only even when exactly one is even or all are even, therefore at least one of them is even, but there is only one even prime number, and therefore without loss of generality assume that $p_{1} = 2$ so we have $n + 2 = 2 + p_{2} + p_{3}$ and therefore $n = p_{2} + p_{3}$ as needed.

p Minus one Factorial is Congruent to Minus one Mod p

Suppose that

p \in ℕ_{2}

is prime, then

(p - 1)! \equiv - 1 (\mod p)

Recall that $S = {0, \dots, p - 1}$ is a complete set of residues mod $p$ , and also for any $s \in S$ since $\gcd (s, p) = 1$ then the collection $T = {0, s, \dots s (p - 1)}$ is a complete system of residues mod $p$ . Since it is then there is exactly one element $j \in T$ such that $j \equiv 1 (\mod p)$ specifically $j = s t$ where $t \in S$ so we can say that $s t \equiv 1 (\mod p)$ .

In the previous paragraph we've shown the existance of a function $f : S \to S$ such that $x f (x) \equiv 1 (\mod p)$ . We're going to prove this function is injective, that is we will prove that if $x, y \in S$ then $f (x) = f (y) ⟹ x = y$ . Suppose that $f (x) = f (y)$ therfore $f (x) \equiv f (y) (\mod p)$ moreover by the definition of $f$ we know that $x f (x) \equiv 1 \equiv y f (y) (\mod p)$ therefore we have $x f (x) \equiv y f (y) \equiv y f (x) (\mod p)$ thus since $f (x) \in S$ we know that $\gcd (f (x), p) = 1$ therefore $x \equiv y (\mod \frac{p}{1})$ so that $x = y$ as needed. As a side note since the size of the domain is the same as the size of the range, then we know that $f$ is a bijection.

For a moment let's consider the case when $f (x) = x$ if that were true we have $x f (x) \equiv x^{2} \equiv 1 (\mod p)$ therefore $x \equiv \pm 1 (\mod p)$ if $x \equiv 1 (\mod p)$ this means that $p | x - 1$ , if $x - 1 \neq 0$ then we know that $p \leq | x - 1 |$ , since $x \in S$ then $x - 1 \in {- 1, \dots p - 2}$ so that $| x - 1 | \leq p - 2$ but then we deduced that $p \leq p - 2$ which is a contradiction so that we must have $x - 1 = 0$ so that $x = 1$ . On the other hand if we know that $x \equiv - 1 (\mod p)$ then we see that $p | x + 1$ since $x + 1 \in {1, \dots, p}$ then the only possibility is that $x + 1 = p$ which is that $x = p - 1$ .

The result of the above paragraph is that if $f (x) = x$ then the only possibility is that $x = 1$ or that $x = p - 1$ , so $x \in {2, \dots, p - 2} ⟹ f (x) \neq x$ and $f (x) \in {2, \dots, p - 2}$ , and this function is a bijection, remaining a bijection on the restriction of the domain and range to ${2, \dots, p - 2}$ .

For a moment note that if $p = 2$ this whole question is trivial because $(2 - 1)! \equiv - 1 (\mod 2)$ , therefore we can assume that $p \geq 3$ also this implies that $p$ is odd, therefore when we consider the collection $K = {2, \dots, p - 2}$ then since $| K | = p - 2 - 2 + 1 = p - 3$ then the size of $K$ is even since $p$ is odd. Let $k_{1} \in K$ then $f (k_{1}) \neq k$ , Let $K_{1} = K ∖ {k_{1}, f (k_{1})}$ , since $f$ is a bijection, then by repeating this process $l = \frac{| K |}{2}$ times then $K_{l} = \emptyset$ which is to say that ${{k_{i}, f (k_{i})} : i \in [1, \dots, l]}$ is a partition of $K$ , thus $2 \dots (p - 2) = \prod_{i = 1}^{l} k_{i} f (k_{i})$ But we see $\prod_{i = 1}^{l} k_{i} f (k_{i}) \equiv \prod_{i = 1}^{l} 1 \equiv 1 (\mod p)$ and therefore $2 \dots (p - 2) \equiv 1 (\mod p)$ therefore $(p - 1)! \equiv 2 \dots (p - 2) (p - 1) \equiv 1 (p - 1) \equiv - 1 (\mod p)$ as needed.

The above is usually referred to "Wilsons Theorem".

p Minus two Factorial is Congruent to One Mod p

Suppose that

p \in ℕ_{2}

is prime, then

(p - 2)! \equiv 1 (\mod p)

Recall that

(p - 1)! \equiv - 1 (\mod p)

but at the same time we know that

(p - 1)! \equiv (p - 1) (p - 2)! \equiv - 1 (p - 2)!

therefore multiplying both sides by

- 1

we obtain that

(p - 2)! \equiv 1 (\mod p)

This allows us to conclude things like: $15! \equiv 1 (\mod 17)$ .

Factorial Fun

Find the remainder when

4 (29!) + 5!

is divided by

31

We know that

29! \equiv 1 (\mod 31)

and that

5! = 120

therefore

4 (29!) + 5! \equiv 124 \equiv 4 (31) \equiv 0 (\mod 31)

1 2 3 n go

Show that for any

n \in ℕ_{2}

then

n | 2 (n - 3)! + 1

iff

n

is prime

Suppose that

n

is prime, therefore

(n - 2)! \equiv 1 (\mod n)

we also know that

n - 2 \equiv - 2 (\mod n)

therefore we know that

(n - 3)! (- 2) \equiv 1 (\mod n) ⟺ 2 (n - 3)! \equiv - 1 (\mod n)

thus

2 (n - 3)! + 1 \equiv 0 (\mod n)

as needed.

For the other direction assume that $n | 2 (n - 3)! + 1$ therefore we know that $2 (n - 3)! \equiv - 1 (\mod n)$ by multiplying both sides by -1, re-writing the factorial and then multiplying by -1 again, we obtain that $(n - 1)! \equiv - 1 (\mod n)$ therefore by wilsons theorem we know that $n$ is prime.

Generalized Wilson's Theorem

Suppose that

p \in ℙ

and that

a \in [1, \dots, p]

then we have

(a - 1)! (p - a)! \equiv {(- 1)}^{a}

We know that the base case holds. Therefore we move directly to the induction step, where we assume that the statement holds true for

k \in ℕ_{1}

, and we have to prove that

(k)! (p - k - 1)! \equiv {(- 1)}^{k + 1}

We have that

\begin{matrix} {(- 1)}^{k} & a m p; \equiv (k - 1)! (p - k)! \\ \equiv (k - 1)! (p - k) (p - k - 1)! \\ \equiv (k - 1)! (- k) (p - k - 1)! \\ \equiv (- 1) k! (p - k - 1)! \end{matrix}

thus by multiplying both sides by

- 1

we obtain that

k! (p - k - 1) \equiv (- 1) k + 1

as needed.

Wilson Folded in Half

Suppose that

p \in ℕ_{3}

is prime, then

{[(\frac{p - 1}{2})!]}^{2} \equiv {(- 1)}^{\frac{p + 1}{2}} (\mod p)

Observe that

\frac{p - 1}{2}, \frac{p + 1}{2} \in ℕ_{1}

since

p

is odd. Since

1 < p

then we know

2 < p + 1 < 2 p

so that

1 < \frac{p + 1}{2} < p

, similarly since

3 \leq p

then

2 \leq p - 1 < p

so that

1 \leq \frac{p - 1}{2} < \frac{p}{2} < p

, moreover

\frac{p - 1}{2} + 1 = \frac{p + 1}{2}

therefore we have:

(p - 1)! = 1 \cdot 2 \dots (\frac{p - 1}{2}) \cdot (\frac{p + 1}{2}) \dots (p - 1)

focusing on the terms that come after $\frac{p - 1}{2}$ in the above product we see $\begin{matrix} \frac{p + 1}{2} & a m p; \equiv - \frac{p - 1}{2} (\mod p) \\ a m p; ⋮ \\ p - 2 & a m p; \equiv - 2 (\mod p) \\ p - 1 & a m p; \equiv - 1 (\mod p) \end{matrix}$ that first congruence comes from the fact that $\frac{p + 1}{2} = p - \frac{p - 1}{2}$ , and notice that they are congruent to the negative versions of the terms in the first half of the factorial, and so we can "fold" it in half to get $(p - 1)! \equiv 1 \cdot (- 1) \cdot 2 \cdot (- 2) \dots (\frac{p - 1}{2}) (- \frac{p - 1}{2}) (\mod p)$ Since there are exactly $\frac{p - 1}{2}$ negative terms we can factor a $- 1$ out from all of them, leaving square of the consecutive numbers so that $(p - 1)! \equiv {(- 1)}^{\frac{p - 1}{2}} {(1 \cdot 2 \dots \frac{p - 1}{2})}^{2} (\mod p)$ by wilsons theorem we know that $(p - 1)! \equiv - 1 (\mod p)$ therefore we have $- 1 \equiv {(- 1)}^{\frac{p - 1}{2}} {[(\frac{p - 1}{2})!]}^{2} (\mod p)$ since $p$ is odd, then $p - 1$ is even, therefore ${(- 1)}^{p - 1} = 1$ , therefore $\begin{matrix} - 1 {(- 1)}^{\frac{p - 1}{2}} & a m p; \equiv {(- 1)}^{\frac{p - 1}{2}} {(- 1)}^{\frac{p - 1}{2}} {[(\frac{p - 1}{2})!]}^{2} (\mod p) \\ {(- 1)}^{\frac{p - 1}{2} + \frac{2}{2}} & a m p; \equiv {(- 1)}^{p - 1} {[(\frac{p - 1}{2})!]}^{2} (\mod p) \\ {(- 1)}^{\frac{p + 1}{2}} & a m p; \equiv {[(\frac{p - 1}{2})!]}^{2} (\mod p) \end{matrix}$ as needed.

Fermats Helper

Suppose

p \in ℕ_{2}

is prime, and

a \in ℤ

so that

p ∤ a

then

a^{p - 1} \equiv 1 (\mod p)

Recall that

R = {0, \dots, p - 1}

is a complete system or resides mod

p

, and since

\gcd (p, a) = 1

then so is

A = {0, \dots, a (p - 1)}

therefore

\prod_{x \in A ∖ {0}} x \equiv (p - 1)! (\mod p)

But we also know that

\prod_{x \in A ∖ {0}} x = a^{p - 1} (p - 1)!

so we conclude that

(p - 1)! a^{p - 1} \equiv (p - 1)! (\mod p)

But then

a^{p - 1} \equiv 1 (\mod p)

Fermats Helper Mod Exponent

Suppose that

p \in ℕ_{2}

is prime, and

a, b \in ℤ

such that

p ∤ a

then

a^{b} \equiv a^{b % (p - 1)} (\mod p)

By the quotient remainder theorem we know that

b = q (p - 1) + r

where

r = b % (p - 1)

therefore

\begin{matrix} a^{b} & a m p; \equiv a^{q (p - 1) + r} \\ a m p; \equiv a^{q (p - 1)} a^{r} \\ a m p; \equiv {(a^{p - 1})}^{q} a^{r} \\ a m p; \equiv 1^{q} a^{r} \\ a m p; \equiv a^{r} \equiv a^{b % (p - 1)} (\mod p) \end{matrix}

where in the 3rd last line we used fermats helper.

Fermats Little

For any

p \in ℕ_{2}

which is prime, then for any

a \in ℤ

we have

a^{p} \equiv a (\mod p)

Suppose $p | a$ then the statement holds true as $0^{p} \equiv 0 (\mod p)$ . On the other hand if $p ∤ a$ then $a^{p - 1} \equiv 1 (\mod p)$ so by multiplying by $a$ we have $a^{p} \equiv a (\mod p)$

Remainder of Power Plus One

Find the remainder of

11^{104} + 1

modulo

17

Observe that by fermats helper since

17 ∤ 11

we have that

11^{16} \equiv 1 (\mod 17)

since

104 = 16 \cdot 6 + 8

then we see that

11^{104} \equiv {(11^{1} 6)}^{6} {(11)}^{8} \equiv 11^{8} (\mod 17)

since

11^{2} = 121 = 17 \cdot 7 + 2

then

11^{8} \equiv {(11^{2})}^{4} \equiv 16 \equiv - 1 (\mod 17)

therefore

11^{104} + 1 \equiv 0 (\mod 17)

2's and 5's

Show that

2222^{5555} + 5555^{2222}

is divisible by

7

Note that in general $A B \cdot 0101 \dots 01 = A B A B \dots A B$ , therfore note that $5555 = 101 \cdot 55$ and that $2222 = 101 \cdot 22$ .

We use this to simplify each base mod $7$ , we have that $\begin{matrix} 5555 & a m p; \equiv 101 \cdot 55 \\ a m p; \equiv (7 \cdot 14 + 3) \cdot (7 \cdot 7 + 6) \\ a m p; \equiv - 3 (\mod 7) \end{matrix}$

also that $\begin{matrix} 2222 & a m p; \equiv 101 \cdot 22 \\ a m p; \equiv 3 \cdot (7 \cdot 3 + 1) \\ a m p; \equiv 3 \end{matrix}$ therefore we know that $2222^{5555} + 5555^{2222} \equiv {(- 3)}^{5555} + 3^{2222} (\mod 7)$ We will now look at $2222 % 6$ since we know that $2220 % 6 = 0$ then $2222 % 6 = 2$ , we will now look at $5555 % 6$ since we know that that $5550 % 6 = 0$ then $5555 % 6 = 5$ therefore ${(- 3)}^{5555} + 3^{2222} \equiv {(- 3)}^{2} + 3^{- 1} \equiv 5 + 2 \equiv 0 (\mod 7)$

Prime Power Sum

Suppose that

p \in ℙ_{3}

then compute

(1^{p} + 2^{p} + 3^{p} + \dots + {(p - 1)}^{p}) % p

Since for each

x \in [1, \dots, p - 1]

we know that by fermats little theorem that

x^{p} \equiv x (\mod p)

thus we have that

\sum_{i = 1}^{p - 1} i^{p} \equiv \sum_{i = 1}^{p - 1} i \equiv \frac{(p - 1) p}{2} (\mod p)

now since

p \in ℙ_{3}

then we know that

p - 1

is an even number therefore we know that

\frac{p - 1}{2} \in ℤ

therefore we have

\frac{(p - 1) p}{2} \equiv \frac{p - 1}{2} p \equiv 0 (\mod p)

which shows that

(1^{p} + 2^{p} + 3^{p} + \dots + {(p - 1)}^{p}) % p = 0

If a Doesn't Divide p Then Fermats Little Theorem and Fermats Little Helper are Equivalent

Suppose that

p \in ℕ_{2}

is prime and

a \in ℤ

such that

p ∤ a

then

a^{p - 1} \equiv 1 ⟺ a^{p} \equiv a (\mod p)

⟹

Suppose that

a^{p - 1} \equiv 1

then multiply both sides by

a

⟸

Suppose that

a^{p} \equiv a

since

\gcd (a, p) = 1

then

a^{p - 1} \equiv 1 (\mod p)

as needed.

Almost Prime

Show that for any

a \in ℤ

we have

a^{9} \equiv a (\mod 30)

Recall that $30 = 2 \cdot 3 \cdot 5$ , what we will is that we will consider the equations $x \equiv a (\mod 2, 3, 5)$ , trivially for each equation $x = a$ works, and therefore by the chinese remainder theorem any other solution is congruent to $a$ mod 30. Our goal will be to show that $a^{9}$ also satisfies the equations which will allow us to deduce that $a^{9} \equiv a (\mod 30)$

Lets confirm that $a^{9} \equiv a (\mod 2)$ , we do know that $a^{2} \equiv a (\mod 2)$ so that $a^{9} \equiv {(a^{2})}^{4} a \equiv 1 a \equiv a$ as needed. We take a similar approach to $a^{9}$ mod $3$ since we know that $a^{3} \equiv a (\mod 3)$ then $a^{9} = {(a^{3})}^{3} \equiv a$ , finally for $a^{9}$ mod $5$ we have $a^{9} = a^{5} a^{4} \equiv a a^{4} \equiv a^{5} \equiv a$ as needed.

Therefore we've deduced that $x = a^{9}$ is also a solution, and therefore $a^{9} \equiv a (\mod 30)$

Carmichael

We say that

n \in ℕ_{1}

is carmichael if

a^{n} \equiv a (\mod n)

for every

a \in ℤ

, and

n

is not a prime.

561 is Carmichael

As per title.

Our goal is to show that for any $a \in ℤ$ we have $a^{561} \equiv a (\mod 561)$ , we also have to show that $n$ is not a prime, which is true because $561 = 3 \cdot 11 \cdot 17$ . Refocusing on the initial goal, we will prove this is true by considering the equations $x \equiv a (\mod 11, 13, 17)$ and noting that $x = a$ is a solution, and also showing that $x = a^{561}$ is also a solution, and therefore concluding $a^{561} \equiv a (\mod 3 \cdot 11 \cdot 17)$ by the chinese remainder theorem.

Note that if $d | a$ then $d | a^{561}$ and therefore $a^{561} \equiv a (\mod d)$ therefore applying that idea to $d = 3, 11, 17$ we see that if any of them divide $a$ we immediately obtain $a^{561} \equiv a (\mod d)$ .

Otherwise things still work, for if $3 ∤ a$ then we know that $a^{2} \equiv 1 (\mod 3)$ since $560$ is even then $a^{560} \equiv {(a^{2})}^{280} \equiv 1$ so we have $a^{561} \equiv a (\mod 3)$ . Similarly if $11 ∤ a$ then $a^{10} \equiv 1 (\mod 11)$ and therefore $a^{560} \equiv 1$ so that $a^{561} \equiv a (\mod 11)$ . Finally if $17 ∤ a$ then we have $a^{16} \equiv 1 (\mod 17)$ and $a^{560} \equiv {(a^{16})}^{35} \equiv 1$ so that $a^{561} \equiv a (\mod 17)$ .

What we've shown is that no matter what we have that $a^{5} 61 \equiv a (\mod 3, 11, 17)$ and therefore by our original paragraph we are done.

Korselt's Criterion

n \in ℕ_{1}

is Carmichael if and only if

n

is squarefree and for every prime

p

such that

p | n ⟹ p - 1 | n - 1

1729 is Carmichael

As per title.

As it turns out

1729 = 7 \cdot 13 \cdot 9

, therefore it is square free and since

6, 12, 8 | 1728

then it is carmichael

Fermats Compositeness Test

Suppose

n, a \in ℤ

such that

\gcd (a, n) = 1

then if

a^{n - 1} \equiv̸ 1 (\mod n)

then

n

is composite

Observe the contrapositive of fermats little helper which states that

a^{p - 1} \equiv̸ 1 ⟹ (p | a \lor p is not prime)

from this we conclude that

(p | a \lor p is not prime)

but since

\gcd (a, n) = 1

then

n ∤ a

therefore we must conclude that

n

is not prime, and therefore composite.

Fermat Witness

n, a

passes the compositeness test, then

a

is said to be a Fermat Witness for

n

Pseudoprime to base

a

Suppose that

n, a \in ℤ

and that

a^{n - 1} \equiv 1 (\mod n)

and

n

is not prime, then

n

is called a pseudoprime to base

a

Most of the time when you find that $a^{n - 1} \equiv 1 (\mod n)$ , then $n$ is prime, that's why the ones that aren't are called pseudoprimes.

341

is a Pseudoprime to base

2

As per title.

Firstly we note that $341$ is divisible by $11$ because $3 - 4 + 1 = 0$ and therefore $341 = 11 \cdot 31$ now we'll verify that $2^{340} \equiv 1 (\mod 341)$ , note that $341 \cdot 3 = 1023$ and since $2^{1} 0 = 1024$ so that $1024 \equiv 1 (\mod 341)$ thus we know that $2^{1} 0 \equiv 1 (\mod 341)$ therefore $3^{340} \equiv {(3^{1} 0)}^{3} 4 \equiv 1 (\mod 341)$ .

On the other hand $3^{341} \equiv̸ 3 (\mod 341)$ , we can see this is true by using the chinese remainder theorem on the equations $x \equiv 3 (\mod 11)$ and $x \equiv 3 (\mod 31)$ and noting that $341$ solves it, but also the switch summation also solves it but the switch is not congruent to 3, so it works.

Fermat Primality Test

Let

n \in ℕ_{2}

, and define the following function

f (X)

if $X = \emptyset$ return $T$
let $a \in X$
if $a^{n - 1} \equiv̸ 1 (\mod n)$ return $F$
return $f (X ∖ {a})$

Let

G = {x \in [1, \dots, n - 2] : \gcd (x, n) = 1}

. If

f (G) = F

then

n

is composite, otherwise we say that

n

is a probable prime

Every Carmichael Number is a Probable Prime

Suppose

n \in ℕ_{1}

is Carmichael, then using the Fermat Primality Test, it is a probable prime.

Since

n

is Carmichael we know that

a^{n} \equiv a (\mod n)

for any

a \in ℤ

, during the test each

a

has the property that

\gcd (a, n) = 1

therefore

a^{n - 1} \equiv 1 (\mod n)

, this means at each stage in the test line 4 is reached until it terminates at line 1 and returning

T

therefore

n

is a probable prime.

At Least Half of the Tested Elements will be Witnesses to a Composite Non-Carmichael Number

Suppose that

n \in ℕ_{1}

is composite and not Carmichael and let

G = {g \in [1, \dots, n - 1] : \gcd (g, n) = 1}

and

W = {w \in G : w^{n - 1} \equiv̸ 1 (\mod n)}

, then

| W | \geq \frac{| G |}{2}

To prove this true, we will consider the set $L = {l \in G : l^{n - 1} \equiv 1 (\mod n)}$ , and note that $G = L ⊔ W$ then if we are able to show that $| L | \leq | W |$ then we have $| G | \leq | L | + | W | \leq 2 | W |$ and we would deduce that $| W | \geq \frac{| G |}{2}$

Since $L \subseteq [0, \dots, n - 1]$ then all elements are incongruent mod $n$ , let $w \in W \subseteq G$ this can be done because $W$ is non-empty as $n$ is not carmichael so that there exists an element $g \in G$ such that $g^{n - 1} \equiv̸ 1 (\mod n)$ .

Since $\gcd (w, n) = 1$ then the collection of elements $w L = {w l : l \in L}$ are also incongruent mod $n$ , since equality implies congruent, then non-congruent implies not equal, and therefore $w L$ generates a collection of unique elements, so that $| L | = | w L |$ .

But note, given some $w l \in w L$ we have that ${(w l)}^{n - 1} \equiv w^{n - 1} l^{n - 1} \equiv w^{n - 1} \equiv̸ 1 (\mod n)$ therefore we deduce that $w L \subseteq W$ so then $| w L | \leq L$ therefore $| L | \leq | W |$ , so that by our introductory paragraph, we've proven what we needed to.

Every Odd Number is a Difference of Squares

For any

n \in ℕ_{1}

that is odd there exists

x, y \in ℕ_{1}

such that

n = x^{2} - y^{2}

Since

n

is odd, then there is some

k \in ℤ

such that

n = 2 k + 1

, note that

2 k + 1

is similar to

{(k + 1)}^{2} = k^{2} + 2 k + 1

and so that

2 k + 1 = {(k + 1)}^{2} - k^{2}

as needed. Note that in this proof

k = \frac{n - 1}{2}

and

k + 1 = \frac{n + 1}{2}

so we are really saying that

n = {(\frac{n + 1}{2})}^{2} + {(\frac{n - 1}{2})}^{2}

The Sum is less than or Equal to the Product

Suppose that

a, b \in ℕ_{2}

then

a + b \leq a \cdot b

a < b

b < a

then

a + b < a \cdot b

Suppose that

a, b \in ℕ_{2}

and without loss of generality assume that

a \leq b

therefore

a + b \leq b + b \leq 2 b \leq a b

Now suppose that

a < b

a + b < b + b = 2 b \leq a b

Fermats Factorization

Suppose that

n \in ℕ_{2}

is odd, then

n

is composite iff there exists

x, y \in ℕ_{1}

such that

n = x^{2} - y^{2}

where

x \neq \frac{n + 1}{2}

$⟹$ We can't use the fact that every odd number is a difference of squares, this is because the solution to that equation was specifically $x = \frac{n + 1}{2}$ which is explicitly disallowed for this proposition, therefore instead we note that $n$ is composite so there exists $c, d \in [2, \dots, n - 1]$ such that $n = c d$ . But at the same time, we know that $\begin{matrix} {(\frac{c + d}{2})}^{2} - {(\frac{c - d}{2})}^{2} & a m p; = \frac{c^{2} + 2 c d + d^{2} - c^{2} + 2 c d - d^{2}}{4} = c d \end{matrix}$ We'll now prove that $\frac{c + d}{2} \neq \frac{n + 1}{2}$ .

Since $c, d \in ℕ_{2}$ then we know that $c + d \leq c \cdot d = n$ so that $c + d < n + 1$ therefore $\frac{c + d}{2} \neq \frac{n + 1}{2}$ as needed.

$⟸$ Suppose that $n = x^{2} - y^{2}$ since $n \geq 2$ then we know $x > y$ also note that $x^{2} - y^{2} = (x + y) (x - y)$ therefore $(x + y) | n$ and $(x - y) | n$ , if $n$ were to be prime, then $(x + y), (x - y) \in {1, n}$ without loss of generality suppose that $x - y = 1$ and $x + y = n$ therefore $2 x = n + 1$ so $x = \frac{n + 1}{2}$ then $y = \frac{n - 1}{2}$ which is a contradiction, and therefore $n$ must be composite.

            
import math

def fermat_factor(n):
    assert n % 2 != 0, "Fermat's factorization method works only for odd integers."

    print(f"Starting Fermat's factorization for n = {n}")

    # Calculate the ceiling of the square root of n
    x = math.ceil(math.sqrt(n))
    print(f"Initial x (ceiling of the square root of n): {x}")

    if x * x == n:
        print(f"{n} is a perfect square. Factors are {x} and {x}.")
        return x, x

    y2 = x * x - n
    print(f"Initial y^2 = {x}^2 - {n} = {y2}")

    # Loop will always terminate because (x, y) = ((n + 1) / 2, (n - 1) / 2) is a valid solution
    while not last_two_digits_possible_square(y2) or not is_perfect_square(y2):
        print(f"y^2 = {y2} is not a perfect square. Incrementing y^2 and then x.")

        # Update y^2 incrementally
        y2 += 2 * x + 1  # Efficiently calculate the next y2 using (x+1)^2 = x^2 + 2x + 1
        x += 1  # Increment x after updating y^2

        print(f"New x = {x}, new y^2 = {x}^2 - {n} = {y2}")

    y = int(math.isqrt(y2))
    print(f"Found perfect square y^2 = {y2}. y = sqrt({y2}) = {y}")
    print(f"Factors are (x - y) = {x - y} and (x + y) = {x + y}")

    return (x - y, x + y)

def last_two_digits_possible_square(n):
    # Set of possible last two digits of a perfect square
    possible_last_two_digits = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81,
                                20, 21, 24, 25, 29, 41, 44, 45, 61, 69, 84}
    return (n % 100) in possible_last_two_digits

def is_perfect_square(n):
    # Check if the number is a perfect square
    root = int(math.isqrt(n))
    return root * root == n

# Example usage:
n = 5959
factors = fermat_factor(n)
print(f"The factors of {n} are {factors}")