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.

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}: