ENT Flashcards
Successor
takes element and gives next element
Principle of mathematical induction
P(n) is a statement about n, for each n in N(0). If P(0) is true and if P(n) implies P(n+1), for all n in N(0), then P(n) is true for all n in N(0).
PMI variants:
Start at P(1) instead of P(0), change N(0) to N. If P(1) is true and if P(x) for all x<n implies P(n), for all n in N, then P(n) is true for all n in N
Well ordering principle
Let S be a non-empty subset of N(0). Then S has a smallest element.
Divisibility DEFINITION
a divides b (a|b) if there exists a d is Z such that b = ad. a is a factor of b, b is a multiple of a
Let a be in Z and b be in N. There exists integers q(quotient) and r (remainder) such that a =
q*b +r. 0<=r<b
a,b in Z. a common divisor of a and b is any integer d such that
d|a and d|b
greatest common divisor gcd(a,b) is the
maximal common divisor
if gcd(a,b) = 1, a and b are
coprime
Euclidean Alogrithm
a = q1b +r1. b=q2r1+r2. r1 = q3r1 + r2 …… r(n-2) = qnr(n-1) + rn. There exists a smallest n such that r(n) = 0 so gcd(a,b) = r(n-1) so gcd(a,b) = ax +by
n is called prime if
n >1 and d|n for d in N then d = 1 or d = n.
if n is not prime it is called
composite
every natural number has at least one
prime divisor. smallest divisor of n is prime
Infinitude of Primes theorem
There are infinitely many primes
there are infinitely many primes of the form
4n - 1
Dirichlet Theorem
a,b are coprime. Then there exist infinitely many primes of the form an +b.
Euclids lemma
Let p be in N, with p>1. Then p is a prime if and only if for all a,b is in Z, we have p |ab then p |A or p|b or both
p is a prime and a1,—,an is in Z then if p|a1 ….an then
p|ai for some 1<= i < n
Fundamental Theorem of Arithmetic
n is in N, n>1. The n can be written is a product of primes. n = p1^(e1) ….. pr^(er).
A pythagorean triple is a solution of the equation
x^2 +y^2 = z^2. it is primitive if gcd(x,y,z) = 1
primitive triples one of x and y is always
even and z is odd
THEOREM: All the primitive pythagoreon triples with 2|x are
x = 2st, y = s^2 - t^t, z = s^2 +t^2. for integers s > t >= 1 such that gcd(s,t) = 1 and s does not equal t (mod 2)
Fermats Theorem x^4 +y^4 = z^2 has no
solutions in natural number
Diophantine equations
x^n + y^n = z^n.
congruences are only defined for
integers
a,b,c in Z and n in N such that gcd(c,n) = 1 then
ac =- bc (mod n) implies a=-b (mod)n
complete set of residues mod n is a subset R in Z
of size n whose remainders mod n are all different
for a,b in Z and n in N coprime to a, the linear congruence has a
unique solution up to adding multiples of n
Method for solving linear congruence, gcd(a,n) = 1
Use Euclidean Algorithm to find u,v such that au + nv = 1. then au =- 1 (mod n) so a(ub) =- b (mod n) hence a solution is x = ub (mod n).
linear congruence is solvable iff
gcd(a,n) | b
Eulers phi function is the number of positive integers….
up to n which are coprime to n.
let n in N and a in Z be coprime to n. Multiplicative order of a mod n ord(a) is smallest d such that
a^d =- 1 (mod n).
if a^d =- 1 (mod n) for some d then
ord(a) | d and ord(a) | phi(n)
gcd(a,d) = 1 the a is primitive root mod n
if ord_n(a) = phi(n)
p is a prime any non-zero polynomial f(x) of degree n with integer coefficients has at most
n roots mod p so f(x) =- 0 (mod p) has at most n solutions mod p
for a divisor d of p-1, the congruence x^d - 1 =-0 (mod p) has exactly
d solutions mod p
p is a prime, then how many primitive roots mod p?
phi(p-1)
g is a primitive root mod p. any a in Z coprime to p can be written as
a =- g^r (mod p) for some r in N
primitive roots exist mod n iff n is
2, 4, p^k, 2p^k for an odd prime p and k in N
p is a prime and a in Z is coprime to p. a is a quadratic residue mod p if
there exists an x in Z such that x^2 =- a (mod p). otherwise a is a quadratic non-residue
0 is neither a QR nor an NR because
gcd(0,p) does not equal 1
for an odd prime p there are exactly how many QRs mod p?
p - 1 / 2
Algorithm for calculating legendre (a/p)
divide a by p with remainder, if r = 0 then it is 0. if r = 1 then it is 1. if r is not 0 or 1 then factorise r r = q1^e1 ….. qk(ek) so it is a product of (q(i)/p)^(ei) from 1 to k. Calculate each factor of the product. if q(i) = 2, 2/p = (-1)^(p^2-1/8) go to next factor. if q(i) > 2 see page 33
there are infinitely many primes of the form
4n +1
if m and n are sums of two squares then so is
mn
p is odd prime. p is a sum of two squares iff
p =-1 (mod 4)
every prime p =- 1 (mod 4) can be represented i=uniquely as a
sum of two squares
n = p1p2…pk * N^2. n is a sum of 2 squares iff
p(i) = 2 or p(i) =- 1 (mod 4) for all i = 1, …., k
any rational number a/b can be written as a
finite simple continued fraction
An infinite continued fraction is the limit of the
convergents C(n)
for an infinite simple CF, this limit always
exists
if d in Pells equation is not a square then the continued fraction expansion of sqrt(d) is
periodic with initial part consisting of only a(0)
ord(n)(a) <=
phi(n)
