1.6 Number Theory

Divisibility

Definition

For integers $a comma b$ with $b is not equal to 0$ , $b$ divides $a$ denoted $b divides a$ if $there exists k is a member of the integers colon a equals k b$ .

Properties

If $b divides a$ and $c divides d$ , then $b c divides a d$
If $b divides a$ , then $b divides a plus b n$ for any $n is a member of the integers$ .
If $b divides a$ and $b divides c$ , then $b divides open paren a x plus c y close paren$ for all $x y is a member of the integers$ .

Greatest Common Divisor (GCD) and LCM

Definition

For $a comma b$ , the greatest common divisor $the gcd of open paren a comma b close paren$ is the largest $d$ such that $d divides a$ and $d divides b$ . The least common multiple $the lcm of open paren a comma b close paren$ is the smallest positive $m$ with $a divides m$ and $b divides m$ .

Euclidean Algorithm

Compute $the gcd of open paren a comma b close paren$ by repeated division: $a equals b q plus r$ , then replace $open paren a comma b close paren left arrow open paren b comma r close paren$ until remainder $0$ .

Relation

$the gcd of open paren a comma b close paren times the lcm of open paren a comma b close paren equals the absolute value of a comma b$

Primes and Fundamental Theorem

Prime

An integer $p is greater than 1$ whose only positive divisors are $1$ and $p$ .

Fundamental Theorem of Arithmetic

Every integer $n is greater than 1$ has a unique factorization into primes up to order:

$n equals p sub 1 raised to the e sub 1 power dot dot dot p sub k raised to the e sub k power$

Modular Arithmetic

For modulus $m is greater than 0$ , define equivalence $a is identical to b mod m$ if $m divides open paren a minus b close paren$ . Operations respect congruence: if $a is identical to a prime$ and $b is identical to b prime$ then $a plus or minus b is identical to a prime plus or minus b prime$ , $a b is identical to a prime b prime mod m$ .

Residue Classes

The set $the set 0 comma 1 comma dot dot dot comma m minus 1$ are representatives of $the integers divided by m the integers$ .

Euler's Totient Function

$phi of m$ number of integers in $the set 1 comma 2 comma dot dot dot comma m$ relatively prime to $m$ . If $m equals the product of p raised to the e sub i power$ then

$phi of m equals m the product over i of open paren 1 minus the fraction with numerator 1 and denominator p sub i close paren$

Congruences and Linear Equations

Solve $a x is identical to b mod m$ . A solution exists iff $the gcd of open paren a comma m close paren divides b$

; then there are $the gcd of open paren a comma m close paren$ solutions mod $m$ .

Chinese Remainder Theorem

If $m sub 1 comma dot dot dot comma m sub k$ are pairwise coprime, the system

$x is identical to a sub i the mod of open paren m sub i close paren semicolon i equals 1 comma dot dot dot k$

has a unique solution mod $M equals the product of m sub i$ .

Diophantine Equations

Linear: $a x plus b y equals c$ has integer solutions iff $the gcd of open paren a comma b close paren divides c$ , general solution from one particular.