ENT

Question 1

Successor

Answer 1

takes element and gives next element

Question 2

Principle of mathematical induction

Answer 2

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).

Question 3

PMI variants:

Answer 3

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

Question 4

Well ordering principle

Answer 4

Let S be a non-empty subset of N(0). Then S has a smallest element.

Question 5

Divisibility DEFINITION

Answer 5

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

Question 6

Let a be in Z and b be in N. There exists integers q(quotient) and r (remainder) such that a =

Answer 6

q*b +r. 0<=r<b

Question 7

a,b in Z. a common divisor of a and b is any integer d such that

Answer 7

d|a and d|b

Question 8

greatest common divisor gcd(a,b) is the

Answer 8

maximal common divisor

Question 9

if gcd(a,b) = 1, a and b are

Answer 9

coprime

Question 10

Euclidean Alogrithm

Answer 10

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

Question 11

n is called prime if

Answer 11

n >1 and d|n for d in N then d = 1 or d = n.

Question 12

if n is not prime it is called

Answer 12

composite

Question 13

every natural number has at least one

Answer 13

prime divisor. smallest divisor of n is prime

Question 14

Infinitude of Primes theorem

Answer 14

There are infinitely many primes

Question 15

there are infinitely many primes of the form

Answer 15

4n - 1

Question 16

Dirichlet Theorem

Answer 16

a,b are coprime. Then there exist infinitely many primes of the form an +b.

Question 17

Euclids lemma

Answer 17

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

Question 18

p is a prime and a1,—,an is in Z then if p|a1 ….an then

Answer 18

p|ai for some 1<= i < n

Question 19

Fundamental Theorem of Arithmetic

Answer 19

n is in N, n>1. The n can be written is a product of primes. n = p1^(e1) ….. pr^(er).

Question 20

A pythagorean triple is a solution of the equation

Answer 20

x^2 +y^2 = z^2. it is primitive if gcd(x,y,z) = 1

Question 21

primitive triples one of x and y is always

Answer 21

even and z is odd

Question 22

THEOREM: All the primitive pythagoreon triples with 2|x are

Answer 22

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)

Question 23

Fermats Theorem x^4 +y^4 = z^2 has no

Answer 23

solutions in natural number

Question 24

Diophantine equations

Answer 24

x^n + y^n = z^n.

Question 25

congruences are only defined for

Answer 25

integers

Question 26

a,b,c in Z and n in N such that gcd(c,n) = 1 then

Answer 26

ac =- bc (mod n) implies a=-b (mod)n

Question 27

complete set of residues mod n is a subset R in Z

Answer 27

of size n whose remainders mod n are all different

Question 28

for a,b in Z and n in N coprime to a, the linear congruence has a

Answer 28

unique solution up to adding multiples of n

Question 29

Method for solving linear congruence, gcd(a,n) = 1

Answer 29

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).

Question 30

linear congruence is solvable iff

Answer 30

gcd(a,n) | b

Question 31

Eulers phi function is the number of positive integers….

Answer 31

up to n which are coprime to n.

Question 32

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

Answer 32

a^d =- 1 (mod n).

Question 33

if a^d =- 1 (mod n) for some d then

Answer 33

ord(a) | d and ord(a) | phi(n)

Question 34

gcd(a,d) = 1 the a is primitive root mod n

Answer 34

if ord_n(a) = phi(n)

Question 35

p is a prime any non-zero polynomial f(x) of degree n with integer coefficients has at most

Answer 35

n roots mod p so f(x) =- 0 (mod p) has at most n solutions mod p

Question 36

for a divisor d of p-1, the congruence x^d - 1 =-0 (mod p) has exactly

Answer 36

d solutions mod p

Question 37

p is a prime, then how many primitive roots mod p?

Answer 37

phi(p-1)

Question 38

g is a primitive root mod p. any a in Z coprime to p can be written as

Answer 38

a =- g^r (mod p) for some r in N

Question 39

primitive roots exist mod n iff n is

Answer 39

2, 4, p^k, 2p^k for an odd prime p and k in N

Question 40

p is a prime and a in Z is coprime to p. a is a quadratic residue mod p if

Answer 40

there exists an x in Z such that x^2 =- a (mod p). otherwise a is a quadratic non-residue

Question 41

0 is neither a QR nor an NR because

Answer 41

gcd(0,p) does not equal 1

Question 42

for an odd prime p there are exactly how many QRs mod p?

Answer 42

p - 1 / 2

Question 43

Algorithm for calculating legendre (a/p)

Answer 43

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

Question 44

there are infinitely many primes of the form

Answer 44

4n +1

Question 45

if m and n are sums of two squares then so is

Answer 45

mn

Question 46

p is odd prime. p is a sum of two squares iff

Answer 46

p =-1 (mod 4)

Question 47

every prime p =- 1 (mod 4) can be represented i=uniquely as a

Answer 47

sum of two squares

Question 48

n = p1p2…pk * N^2. n is a sum of 2 squares iff

Answer 48

p(i) = 2 or p(i) =- 1 (mod 4) for all i = 1, …., k

Question 49

any rational number a/b can be written as a

Answer 49

finite simple continued fraction

Question 50

An infinite continued fraction is the limit of the

Answer 50

convergents C(n)

Question 51

for an infinite simple CF, this limit always

Answer 51

exists

Question 52

if d in Pells equation is not a square then the continued fraction expansion of sqrt(d) is

Answer 52

periodic with initial part consisting of only a(0)

Question 53

ord(n)(a) <=

Answer 53

phi(n)