ENT Flashcards

1
Q

Successor

A

takes element and gives next element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Principle of mathematical induction

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

PMI variants:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Well ordering principle

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Divisibility DEFINITION

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

d|a and d|b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

greatest common divisor gcd(a,b) is the

A

maximal common divisor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

coprime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Euclidean Alogrithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

n is called prime if

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

if n is not prime it is called

A

composite

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

every natural number has at least one

A

prime divisor. smallest divisor of n is prime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Infinitude of Primes theorem

A

There are infinitely many primes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

there are infinitely many primes of the form

A

4n - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Dirichlet Theorem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Euclids lemma

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

p|ai for some 1<= i < n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Fundamental Theorem of Arithmetic

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

A pythagorean triple is a solution of the equation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

primitive triples one of x and y is always

A

even and z is odd

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

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)

23
Q

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

A

solutions in natural number

24
Q

Diophantine equations

A

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

25
congruences are only defined for
integers
26
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
27
complete set of residues mod n is a subset R in Z
of size n whose remainders mod n are all different
28
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
29
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).
30
linear congruence is solvable iff
gcd(a,n) | b
31
Eulers phi function is the number of positive integers....
up to n which are coprime to n.
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
a^d =- 1 (mod n).
33
if a^d =- 1 (mod n) for some d then
ord(a) | d and ord(a) | phi(n)
34
gcd(a,d) = 1 the a is primitive root mod n
if ord_n(a) = phi(n)
35
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
36
for a divisor d of p-1, the congruence x^d - 1 =-0 (mod p) has exactly
d solutions mod p
37
p is a prime, then how many primitive roots mod p?
phi(p-1)
38
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
39
primitive roots exist mod n iff n is
2, 4, p^k, 2p^k for an odd prime p and k in N
40
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
41
0 is neither a QR nor an NR because
gcd(0,p) does not equal 1
42
for an odd prime p there are exactly how many QRs mod p?
p - 1 / 2
43
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
44
there are infinitely many primes of the form
4n +1
45
if m and n are sums of two squares then so is
mn
46
p is odd prime. p is a sum of two squares iff
p =-1 (mod 4)
47
every prime p =- 1 (mod 4) can be represented i=uniquely as a
sum of two squares
48
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
49
any rational number a/b can be written as a
finite simple continued fraction
50
An infinite continued fraction is the limit of the
convergents C(n)
51
for an infinite simple CF, this limit always
exists
52
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)
53
ord(n)(a) <=
phi(n)