+Number theory

Notation

[n]: Set of first n natural numbers.

Themes

About Z.

Properties of Numbers

Evenness and odness. Primes and composites. Unique factorization of n as product of primes: $n=p_1^{e_1}..$.

GCD

gcd(x,y). $gcd(x,y)|x-y$.

Euclid’s algorithm

To find gcd(x, y): if $y|x$ return y else return gcd(x, y-x).

From Euclid’s alg, GCD(x,y)=ax+by. If 1 = ax+by, a $\equiv$ multiplicative inverse of x mod y.

Extended Euclid’s alg

Find a,b using Euclid’s alg.

Diophontine equation

Indeterminate polynomial eqn with integer solutions: eg: gcd(x, y) = ax + by in Euclid’s alg.

Conjectures

Goldbach conjecture: $\mathrm{\forall }x\in N,x>4$, x = sum of 2 primes.

Primes

Special primes

Marsenne prime: writ as $2^n-1$.

Prime number theorem

Num of primes under k = $\mathrm{\Pi }(k)=(1+o(1))\frac{k}{\ln k}$. \why

(Green, Tao) Number of arithmatic progressions of primes of length $\ge k$ is $\ge 1$.

Primality testing of n

Don’t try to factor: assumed hard.

Randomized primality test

(Miller Rabin) Pick rand x in \(Z^{+}{n} - \set{0}\). If $x|n$ reject. See if (Fermat’s little th, Lucas-Lehmer) \(\forall x \in Z{n}^{*}: x^{n-1} = 1 \mod n\) holds: do it in polylog time with repeated squaring. Repeat test with many x’s. In failure, reject. Else, check if it is a Carmichael composite number: see if 1 has a non-trivial square root: Write $n-1=2^{s}d$; pick $x\ne \pm 1$; repeatedly square and check if $x\mathrm{mod}n=1$: if so reject, else if $x\mathrm{mod}n=-1$: try starting with another x.

Picking some prime below N

Pick a random number below n, check if it is a prime: if not prime fail. By Prime number th, this alg has $\approx (\ln n{)}^{-1}$ success rate, which can then be amplified.

Special numbers

Square free integers

Aka quadratfrei. Divisible by no perfect square except 1.

Carmichael composite number

Let prime factorization: $n=p_1^{e_1}..$. Aka Fermat pseudoprimes: They’re Fermat liers: $\mathrm{\forall }a:a^{n-1}\equiv 1\mathrm{mod}n$. n is Carmichael iff it is square free; for all $p_i$ $p_i-1|n-1$. \why Eg: 561 = 31117; $\mathrm{\forall }a:a^{560}=1\mathrm{mod}3,\mathrm{mod}17,\mathrm{mod}11$ as $2,10,16|560$.

Modulo arithmatic

The remainder fn. $-3\equiv 2\mathrm{mod}5$. $ab\mathrm{mod}n\equiv (a\mathrm{mod}n)(b\mathrm{mod}n)\mathrm{mod}n$. So, congruence relation over $\mathbb{Z}$ wrt +, *. If $a\equiv b\mathrm{mod}n⟹n|a-b$.

Cancellation law

$ka\equiv kb\mathrm{mod}n⟹k(a-b)\equiv 0\mathrm{mod}p⟹a\equiv b\mathrm{mod}n$.

Chinese remainder theorem

Let $n_i$’s coprime, $N=\prod _j{n}_j$. System of simultaneous congruences $x=a_i\mathrm{mod}{n}_i$ for $i=1\dots k$ has a unique solution for x in ${\mathbb{Z}}_N$.

Uniqueness

If $\mathrm{\forall }i,x\equiv x_i\mathrm{mod}{n}_i$, and $y\equiv x_i\mathrm{mod}{n}_i$, $x-y\equiv 0\mathrm{mod}N$.

Solving for x

Use Extended Euclid’s alg on $1=r_i{n}_i+s_i\frac{N}{n_i}$ to find $r_i$ and $s_i$, let $e_i=s_i\frac{N}{n_i}$; then $e_i\equiv 1\mathrm{mod}{n}_i$ but $0\mathrm{mod}{n}_j$; thence find $x=\sum _{i=1}^k{a}_i{e}_i$.

Equivalent statements and implications

$|Z_N|\to |{\times }_i{Z}_{n_i}|$. Map $x\to (x\mathrm{mod}{n}_1,..)$ from $Z_N\to {\times }_i{Z}_{n_i}$ is both one to one and onto. Also, Isomorphism by Chinese remainder fn: \(\mathbb{Z}{n} \cong \times{i}\mathbb{Z}{n{i}}\) preserves +, *.

Utility

Useful for manipulating composite numbers. An airthmatic question mod N reduced to arithmatic questions modulo $n_i$, if we know $\left\{n_i\right\}$.

Additive group

\(Z^{+_{p}\) A prime order group. Does not have any subgroups.

Multiplicative group

\(Z_{N^{*}\)

$Z_N^{\ast }$ : N’s coprimes in $1,\dots ,N-1,\ast \mathrm{mod}N$. Proof: GCD with N is 1, so use extended Euclid’s alg to find inverses. If p prime; -1 := p-1; $\sqrt{1}\equiv \pm 1\mathrm{mod}p$.

Order

N=pq; p, q primes: order = totient function: \(|Z^{*}{N}|=\varphi(N)=(p-1)(q-1)\): we discard multiples of p, q. Also, if \(N= \prod p{i}^{e_{i}}\), $\phi (N)=\prod (p_i-1)p_i^{e_i-1}$.

(Euler’s theorem). $a^{\phi (N)}\equiv 1\mathrm{mod}N$: Take $a,a^2\dots a^k=e$; this is a subgroup of $Z_N^{\ast }$; by Lagrange (see group theory in algebra ref), $k|\phi (N)$.

$N=\prod p_i^{e_i}$. $\frac{|Z_N^{\ast }|}{|Z_N^{+}|}=\frac{\phi (N)}{N}=\prod _{i=1}^t\frac{p_i-1}{p_i}\ge \prod _{i=1}^t\frac{i}{i+1}=\frac{1}{1+t}\ge \frac{1}{1+{\log }_{2}N}$.

So, Fermat’s little theorem: p prime: $a^p\equiv a\mathrm{mod}p$.

Primitive roots

Aka generator. If \(S = Z_{n}^{}\), g is primitive root of n. \(Z_{p}^{}\) for prime p always has primitive root \why. 7 has primitive roots 3, 5. $1,2,4,p^k,2p^k$ have primitive roots for p odd prime and $k\ge 1$.\ \why \tbc

The number of primitive roots, if there are any, is $\varphi (\varphi (n))$. (See group theory in algebra ref)

Primitive root test

g is primitive root of n iff its multiplicative order is $\varphi (n)$: else it generates a subgroup. Efficiently see if g is a generator: find prime factors of $\varphi (n)=\prod _i{p}_i$, keep seeing if $g^{\frac{\varphi (n)}{p_i}}=1$.

Quadratic residues

$Q{R}_n$: set of squares mod n. Quadratic non residues. If $a\in Q{R}_n,aRn$, else a N n.

Finding $\sqrt{x}$ same as solving $y^2=x\mathrm{mod}n$, or factoring $(y^2-x)\mathrm{mod}n$.

$Q{R}_p$ for odd prime p

As structure of \(Z_{p}^{}\) cyclic; writable as $\left\{g^i\right\}$ for primitive root g; only even powers $\left\{g^{2i}\right\}$ are squares. So, \(|QR_{p}| = |Z_{p}^{}|/2\).

1 has exactly 2 roots: $\pm 1$, and no more: $x^2-1\mathrm{mod}p=(x-1)\mathrm{mod}p(x+1)\mathrm{mod}p=0$ so x-1 = 0 mod p or x+1 = 0 mod p. $g^{\frac{p-1}{2}}=-1$. $\sqrt{g^{2i}}=\pm g^i$ by Euler thm.

Jacobi symbol

$(\frac{a}{p})$ = 0 if $p|a$; +1 if a R p, $p\nmid a$; -1 if a N p.

Legendre: generalization to n=pq; $(\frac{a}{n})$ = -1 if a N n; if a R n, $(\frac{a}{n})=1$, but can’t tell if a R n given $(\frac{a}{n})=1$.

$Q{R}_n$ for p, q odd primes; n = pq (Blum integer)}

$\mathrm{\exists }4\sqrt{1}$: take $x^2=1\mathrm{mod}n$; $\pm 1$ are obvious roots; Chinese remainder thm solutions s for $x=1\mathrm{mod}p;x=-1\mathrm{mod}q$ and t for $x=-1\mathrm{mod}p;x=+1\mathrm{mod}q$ are the other two. As square roots appear in pairs, s = -t. To find the non trivial square roots, must know p, q.

Similarly, for any odd $m=m_1{m}_2$, 1 has $\ge 4$ roots.

So, any $a^2\in Q{R}_n$ has $\ge 4$ roots: $a\sqrt{1}$. So, $4^{-1}|Z_n^{\ast }|\le |Q{R}_n|$.