# Number Theory on Primes




```python
from math import factorial, log
import numpy as np
import matplotlib.pyplot as plt
%run primes.py
%run ../../python-data-science/display_helpers.py
```


```python
%%timeit -r 1
A = Prime.nth(10000)
B = Prime.nth(20000)
P = A*B

# (104743, 110609, 11585518487)
display(A, B, P)
```


    104743



    224743



    23540256049



    104743



    224743



    23540256049


    13 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)


----

## Wilson's Theorem

- p is prime

$ (p-1)! \equiv p-1 \bmod p$


```python
S = 3000
N = 4000
f = lambda p: (factorial(p-1) % p) / p
x = np.arange(S,N)
y = np.array( [f(p) for p in x] )

plt = configure_plot((S, N), (0, 1.5), figsize=(24, 8))
#plt.plot(x, y, color = 'tomato')
plt.scatter(x, y, s=1)
display(plt)
```

----

## Fermat's Little Theorem

- p is prime
- a, *s.t* p $\nmid$ a ( *is not divisble by*  )

$a^{p-1} \equiv -1 \pmod p$


```python
p = Prime.nth(3000)
a = 2 # not prime is divisble by 2, 2 is also faster for computer
a**(p-1) % p
```




    1



Usage:

Find the remainder when you divide $3^{100,000}$ by 53.

p = 53 is prime, and 53 $\nmid$ 3 so

$\begin{equation}
\begin{split}
3^{53-1} &\equiv 1 \pmod{53}  \\
3^{52} &\equiv 1 \pmod{53}  \\
{ \text{trick: raise both sides to a large power} } \\
\frac{100, 000}{52} : quotient &= 1923, rem =  4 \\
(3^{52})^{1923} &\equiv 1^{1923} \pmod{53} \\
3^{99,996} &\equiv 1 \pmod{53} \\
3^4(3^{99,996}) &\equiv 3^4 \pmod{53} \\
3^{100,000} &\equiv 81 \pmod{53} \\
3^{100,000} &\equiv 28 \pmod{53} \\
\end{split}
\end{equation}
$

Proof:
https://www.youtube.com/watch?v=w0ZQvZLx2KA&list=PLi01XoE8jYojnxiwwAPRqEH19rx_mtcV_&index=3

- p is prime
- a, *s.t* p $\nmid$ a ( *is not divisble by*  )

Every integer is congruent to one of `0, 1, 2, 3, ... p-1 (mod p)`

Use only non-zero congruence classes, because 0 (pod p) contains the multiples of p, and p $\nmid$ a

Multiply all other values `1, 2, 3 ... p-1` with a.

`a, 2a, 3a ... (p-1)a`

show this list is a rearrangement of all the elements in the group.

> case 1: None of these are congruent to 0. <br/>
> suppose $r.a \equiv 0 \pmod p$, then p $\mid$ a, which is a contradiction

> case 2: These are distinct; no two are congruent to each other. <br/>
  > Pick 2 values - r.a, s.a, where 0 < r < p, and 0 < s < p
  > Show that $r.a \not\equiv s.a \pmod p$ 
  > So r.a - s.a = a.(r-s)
  > By assumption, p $\mid$ a
  > Can p divide r-s?
  >    0 < r < p ,   -p < -s < 0   =>  -p < r-s < p
  >    $r -s \ne 0$, therefore $p \nmid r-s$

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

$ a^{p-1} \equiv 1 \pmod p$




----
## The Prime Number Theorem

Definition: P(n) = number of primes $\leq$ n

P(6) = 3
P(10) = 4


```python
S = 2
N = 50000

h = (N / log(N)) * 1.2
r = range(S,N)
pi = Prime.pi()

x = np.arange(S, N)
y = np.array([next(pi) for a in r])
y_asym = x / np.log(x)

plt = configure_plot((0, N), (0, y_asym[-1]*1.2), figsize=(12, 8))
plt.plot( x, y, color = 'tomato')
plt.plot( x, y_asym, color = 'tomato', dashes = [4,4])
display(plt)
```

$P(n) \sim \frac{n}{log n} $

(i.e. ~ is asymptotically equivalent as n approaches infinity)

$\displaystyle  a_n \sim b_n if \lim_{n\to\inf} \frac{a_n}{b_n} = 1$


```python

```

65562499e94a0e5a3f1d74f2cf50ec7cbac2aa48
ipynb
Jupyter Notebook
notebooks/math/number_theory/primes.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/primes.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/primes.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
Qwen/Qwen-72B
1. YES
2. YES