Shreyas’ Notes

Introduction to Number Theory

MATH 365

spring, sophomore year

Divisibility §

Theorem: For integers aa, bb, cc, the following hold:

GCD: for a,bZa, b \in \mathbb{Z}, the GCD is the largest integer that divides both aa and bb. aka the unique integer dd such that: dad \mid a, dbd \mid b, and cacb    cdc \mid a \wedge c \mid b \implies c \leq d.

well-ordered principle:

if gcd(a,b)=1\gcd(a, b) = 1, aa and bb are relatively prime (coprime).

Given a,bZa, b \in \mathbb{Z} st b0b \neq 0, there exist unique integers qq and rr such that a=qb+ra = qb + r and 0r<b0 \leq r < |b|.

Bezout’s Theorem: Let a,bZa, b \in \mathbb{Z} such that they’re not both zero. gcd(a,b)\gcd(a, b) is the smallest positive integer dd that can be written in the form d=ax+byd = ax + by with x,yZx, y \in \mathbb{Z}.

If cc is a common divisor of aa and bb, cgcd(a,b)c \mid \gcd(a, b)

Multiples of gcd(a,b)\gcd(a, b) are precisely the integers of the form ax+byax + by for x,yZx, y \in \mathbb{Z}. In other words, ax+by=cax + by = c has a solution iff gcd(a,b)c\gcd(a, b) \mid c.

aa and bb are relatively prime iff there exist x,yZx, y \in \mathbb{Z} such that ax+by=1ax + by = 1.

If gcd(a,b)=d\gcd(a, b) = d, gcd(ad,bd)=1\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1.

If aba \mid b, bcb \mid c, and gcd(a,b)=1\gcd(a, b) = 1, then abcab \mid c.

Euclid’s Lemma: If abca \mid bc and gcd(a,b)=1\gcd(a, b) = 1, then aca \mid c.

If pp is prime and pabp \mid ab, then papbp \mid a \vee p \mid b.

gcd(a,b)=gcd(a+bq,b)\gcd(a, b) = \gcd(a + bq, b)

Euclid’s Algorithm: Let a,bZa, b \in \mathbb{Z} st they’re not both zero. r1=ar_{-1} = a, r0=br_0 = b. ri+1r_{i + 1} is the remainder of the division algorithm applied to ri1r_{i-1} and rir_i.

Linear equation theorem: Let a,ba, b be non-zero integers with d=gcd(a,b)d = \gcd(a, b). ax+by=dax + by = d always has an integer solution (x0,y0)(x_0, y_0) which can be found using the extended Euclid’s algorithm. All other solutions are of the form (x0+kbd,y0kad)\left(x_0 + k \frac{b}{d}, y_0 - k \frac{a}{d}\right) for kZk \in \mathbb{Z}.

Linear equations where solutions must be integers are called diophantine equations.

If pp is prime and pa1a2anp \mid a_1 a_2 \dots a_n, then pakp \mid a_k for some kk, 1kn1 \leq k \leq n.

If p,q1,q2,,qnp, q_1, q_2, \dots, q_n are prime and pq1q2qnp \mid q_1 q_2 \dots q_n, then p=qkp = q_k for some kk, 1kn1 \leq k \leq n.

Every positive integer (n>1n > 1) can be expressed as a product of primes n=p1p2pnn = p_1 p_2 \dots p_n. This representation is unique up to the order of primes.

Any positive integer n>1n > 1 can be written canonically as n=p1a1prarn = p_1^{a_1} \dots p_r^{a_r} where p1<<prp_1 < \dots < p_r are prime and 0<a1,,an0 < a_1, \dots, a_n.

There are infinitely many primes.

Prime Number Theorem: The function π\pi is asymptotic to xlnx\frac{x}{\ln x}.

The proportion of primes at most nn is  1lnn~ \frac{1}{\ln n}.

Goldbach Conjecture: Every even number n4n \geq 4 can be written as the sum of two primes.

Twin Prime Conjecture: There are infinitely many primes pp such that p+2p + 2 is also prime.

A pythagorean triplet is an integer solution to the equation x2+y2=z2x^2 + y^2 = z^2. A pythagorean triple is called primitive if gcd(x,y,z)=1\gcd(x, y, z) = 1.

Modular Arithmetic §

The least common multiple of a,bNa, b \in \mathbb{N} is the smallest positive integer nn such that ana \mid n and bnb \mid n.

gcd(a,b)=primes ppmin(ap,bp)\gcd(a, b) = \prod_{\text{primes }p} p^{\min(a_p, b_p)}

lcm(a,b)=primes ppmax(ap,bp)lcm(a, b) = \prod_{\text{primes }p} p^{\max(a_p, b_p)}

ab=pap+bp=pmin(ap,bp)+max(ap,bp)=gcd(a,b)lcm(a,b)ab = \prod p^{a_p + b_p} = \prod p^{\min(a_p, b_p) + \max(a_p, b_p)} = \gcd(a, b) \cdot lcm(a, b)

For a given mNm \in \mathbb{N}, two integers a,ba, b are congruent modulo mm if mabm \mid a - b.

abmodma \equiv b \mod m

Every integer is congruent modulo mm to precisely one integer aa where 0<a<m0 < a < m.

The set of integers 0,1,2,,m10, 1, 2, \dots, m - 1 is called the least residue system modulo mm.

a1,a2,,ama_1, a_2, \dots, a_m is a complete residue system modulo mm if every integer is congruent modulo mm to precisely one of aia_i.

abmodma \equiv b \mod m iff aa and bb leavea the same remainder when divided by mm.

Equivalence relation.

for a given mNm \in \mathbb{N}, a,b,c,dZa, b, c, d \in \mathbb{Z}:

If acbcmodmac \equiv bc \mod m and d=gcd(c,m)d = \gcd(c, m), then abmodmda \equiv b \mod \frac{m}{d}

If gcd(c,m)=1\gcd(c, m) = 1 and acbcmodmac \equiv bc \mod m, then abmodma \equiv b \mod m.

If pp is prime and pcp \nmid c, then acbcmodp    abmodpac \equiv bc \mod p \implies a \equiv b \mod p.

Linear Congruences §

axbmodmax \equiv b \mod m

mutually incongruent solutions

If axbmodmax \equiv b \mod m and d=gcd(a,m)d = \gcd(a, m):

axbmodmax \equiv b \mod m has a unique solution modulo mm iff aa and mm are coprime.

Let m>1m > 1, aZa \in \mathbb{Z}. An integer bZb \in \mathbb{Z} is an inverse of of amodma \mod m if ab1modmab \equiv 1 \mod m. aa has an inverse modulo MM iff gcd(a,m)=1\gcd(a, m) = 1.

Fermat’s Little Theorem: if pp is prime and pap \nmid a, then ap11modpa^{p - 1} \equiv 1 \mod p

A solution to ax1modmax \equiv 1 \mod m is called a (multiplicative) inverse of aa modulo mm. aa11modma \cdot a^{-1} \equiv 1 \mod m. Inverses exist only if gcd(a,m)=1\gcd(a, m) = 1.

If gcd(a,m)=1\gcd(a, m) = 1, for any cZc \in \mathbb{Z}, c,c+a,,c+(m1)ac, c + a, \dots, c + (m - 1)a is a complete residue system. Order needn’t match up.

If gcd(a,m)1modm\gcd(a, m) \equiv 1 \mod m and am1≢1modma^{m - 1} \not\equiv 1 \mod m, then mm is composite.

Primality testing: if gcd(a,b)=1\gcd(a, b) = 1 and am11modma^{m - 1} \equiv 1 \mod m, then mm is composite. Test of compositeness: converse is false. Composite numbers for which the test holds are called Carmichael numbers.

Wilson’s Theorem: pp is prime iff (p1)!1modp(p - 1)! \equiv -1 \mod p

The Euler totient ϕ\phi: ϕ(n)=#{a:1an1,gcd(a,n)=1}\phi(n) = \#\{a : 1 \leq a \leq n - 1, \gcd(a, n) = 1\}

Euler’s Theorem: aϕ(m)1modma^{\phi(m)} \equiv 1 \mod m

Chinese Remainder Theorem: Suppose m1,m2,,mr>1m_1, m_2, \dots, m_r > 1 such that gcd(m1,mj)=1\gcd(m_1, m_j) = 1 for iji \neq j. Then, for any integers a1,,ara_1, \dots, a_r, the system xaimodmix \equiv a_i \mod m_i for 1ir1 \leq i \leq r has a solution. Additionally, any solution is unique modulo m1mrm_1 \cdots m_r.

The Euler totient ϕ\phi is multiplicative. if m,nZ+m, n \in \mathbb{Z}^+ and gcd(m,n)=1\gcd(m, n) = 1, ϕ(mn)=ϕ(m)ϕ(n)\phi(mn) = \phi(m) \phi(n).

If pp is prime:

ϕ(n)=npn(11p)\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)

n=dnϕ(d)n = \sum_{d \mid n} \phi(d)


For a,mZa, m \in \mathbb{Z} st gcd(a,m)=1\gcd(a, m) = 1. The order of aa is the smallest positive exponent ee st ae1(modm)a^e \equiv 1 \pmod{m}. ordm(a)ord_m(a).

ak1(modm)a^k \equiv 1 \pmod{m} implies that ordm(a)kord_m(a) \mid k.

ordm(a)ϕ(m)ord_m(a) \mid \phi(m)

Let gcd(a,m)=1\gcd(a, m) = 1. aiaj(modm)    ij(modord(a))a^i \equiv a^j \pmod{m} \iff i \equiv j \pmod{ord(a)}

a,a2,,aord(a)a, a^2, \dots, a^{ord(a)} are distinct modulo mm.

An integer aa (relatively prime to mm) is called a primitive root of mm if ord(a)=ϕ(mord(a) = \phi(m.

If a1,a2,,aϕ(m)a_1, a_2, \dots, a_{\phi(m)} are the positive ints less than mm and coprime to mm and aa is a primitive root of mm, then a,a2aϕ(m)a, a^2 \dots a^{\phi(m)} are congruent to a1,a2,bak(modm)a_1, a_2,b \equiv a^k \pmod{m} \dots, a_{\phi(m)}$ in some order modulo mm. For any integer bb, bak(modm)b \equiv a^k \pmod{m} for some 1kord(a)1 \leq k \leq ord(a).

If mm has a primitive root, then it has exactly ϕ(ϕ(m))\phi(\phi(m)) primtive roots.

Suppose aa is a primitive root of mm. Then aka^k is also a primitive root of mm iff gcd(k,ϕ(m))=1\gcd(k, \phi(m)) = 1.

Lagrange theorem: Let pp be a prime and f(x)=anxn++a0f(x) = a_n x^n + \dots + a_0 where aiZa_i \in \mathbb{Z} and an≢0(modp)a_n \not\equiv 0 \pmod{p}. Then f(x)0(modp)f(x) \equiv 0 \pmod{p} has at most nn solutions modulo pp.

If pp is an odd prime divisor of n2+1n^2 + 1, then p1(mod4)p \equiv 1 \pmod{4}.

If ordn(a)=kord_n(a) = k, then ordn(ah)=kgcd(k,h)ord_n(a^h) = \frac{k}{\gcd(k, h)}

If gcd(h,ordn(a))=1\gcd(h, ord_n(a)) = 1, then ordn(ah)=ordn(a)ord_n(a^h) = ord_n(a).

An integer nn has a primitive root iff n=2,4,pk,2pkn = 2, 4, p^k, 2 p^k where pp is an odd prime.

Let gg be a primitive root of nn and gcd(a,n)=1\gcd(a, n) = 1. age(modn)a \equiv g^e \pmod{n} for some positive ee. The smallest such exponent is called the index of aa mod nn for the base gg. indg(a)ind_g(a). Discrete logarithm.

Indices satisfy:

Theorem: Let nn be an integer with a primitive root and gcd(a,n)=1\gcd(a, n) = 1. Then xka(modn)x^k \equiv a \pmod{n} has a solution iff aϕ(n)d1(modn)a^{\frac{\phi(n)}{d}} \equiv 1 \pmod{n} has a solution where d=gcd(k,ϕ(n))d = \gcd(k, \phi(n)). There are exactly dd solutions.

Quadratic Reciprocity §

There are exactly p12\frac{p - 1}{2} integers aa (pap \nmid a) that are squares modulo pp. These p12\frac{p - 1}{2} integers occur as squares of 12,22,,(p12)21^2, 2^2, \dots, \left(\frac{p - 1}{2}\right)^2.

If pap \nmid a and ab2(modp)a \equiv b^2 \pmod{p} for some bb, then we call aa a quadratic residue modulo pp.

If pp and qq are distinct odd primes, then (p/q)(q/p)=(1)p12q12(p/q)(q/p) = {(-1)}^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}

If pp is an odd prime ad aa is an odd integer st gcd(a,p)=1\gcd(a, p) = 1:

k=1p12kapμ(a,p)(mod2)\sum_{k = 1}^{\frac{p - 1}{2}} \lfloor\frac{ka}{p}\rfloor \equiv \mu(a, p) \pmod{2}

if 2k+12^k + 1 is an odd prime, kk is a power of 2.

a fermat number is a positive integer of the form Fn=2(2n)+1F_n = 2^{(2^n)} + 1. if FnF_n is prime, we FnF_n is a fermat prime.

Jacobi Symbol:

(an)=(ap1)e1(apr)er(a | n) = {(a | p_1)}^{e_1} \cdots {(a | p_r)}^{e_r}

Let a,ba, b be odd positive integers with gcd(a,b)=1\gcd(a, b) = 1.

(ab)={(ba)a1(mod4)b1(mod4)(ba)ab3(mod4)(a | b) = \begin{cases} (b | a) & a \equiv 1 \pmod{4} \vee b \equiv 1 \pmod{4} \\ - (b | a) & a \equiv b \equiv 3 \pmod{4} \end{cases}

(2b)={1b1(mod8)b7(mod8)1b3(mod8)b5(mod8)(2 | b) = \begin{cases} 1 & b \equiv 1 \pmod{8} \vee b \equiv 7 \pmod{8} \\ -1 & b \equiv 3 \pmod{8} \vee b \equiv 5 \pmod{8} \end{cases}

(1b)={1b1(mod4)1b3(mod4)(-1 | b) = \begin{cases} 1 & b \equiv 1 \pmod{4} \\ -1 & b \equiv 3 \pmod{4} \end{cases}

Euler’s criterion doesn’t hold for the Jacobi symbol.

Euler’s primality test: check if ap12±1(modp)a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}

Diophantine Approximation §

Approximate real numbers by rational numbers.

Let α\alpha be an irrational number. Then there exist infinitely many ab\frac{a}{b} st αab<12b2|\alpha - \frac{a}{b} < \frac{1}{2b^2}.

If α\alpha is irrational, the line x=αx = \alpha intersects infinitely many Ford circles.

Continued Fractions §

the continued fraction made from [a0;a1,,an][a_0; a_1, \dots, a_n] by cutting off the expansion after the kk-th partial denominator is called the kk-th convergent of the continued fraction and is denoted as CkC_k

an infinite continued fractino [a0,a1,][a_0, a_1, \dots] is the real number limn[a0;a1,,an]\lim_{n \rightarrow \infty} [a_0; a_1, \dots, a_n]

infinite continued fractions are irrational

all irrational numbers have infinite continued fraction expressions

distinct infinite continued fractions correspond to distinct irrational numbers

Quadratic Forms §

A binary integral quadratic form is a polynomial Q(x,y)=ax2+bxy+cy2Q(x, y) = ax^2 + bxy + cy^2. if n=Q(x,y)n = Q(x, y) has a solution, we say that nn is represented by QQ.

representation problem: given a quadratic form QQ, which integers are represented by QQ?

pairs with gcd greater than one can be reduced to pairs with gcd = 1. pairs with gcd = 1 are called primitive pairs.