Definitions

Question 1

b divides a

Answer 1

Let a and b be integers. If there exists an integer c with a = bc, then we say that b divides a (or a is a multiple of b) and we write this as b | a

Question 2

Common Divisor

Answer 2

Let a, b ∈ Z. If d | a and d | b we say that d is a common divisor of a and b. Let
D(a, b) denote the set of all common divisors of a and b.

Question 3

Greatest Common Divisor

Answer 3

Let a, b ∈ Z. If at least one of a, b is non-zero then we denote the greatest
common divisor of a and b by gcd(a, b).

Question 4

Prime

Answer 4

An integer p > 1 is said to be prime if the only positive divisors of p are 1 and
itself.

Question 5

Finite Continued Fraction

Answer 5

A finite continued fraction is an expression of the form:
xo+1/(x1+1/(x2+1/…))
where xo ∈ R and all other xk are positive real numbers.
We denote the above finite continued fraction by [x0 : x1, x2, . . . , xn].

Question 6

Finite Simple Continued Fraction

Answer 6

A finite simple continued fraction is an expression of the form:
xo+1/(x1+1/(x2+1/…))
where xo ∈ Z and all other xk are positive real numbers.
We denote the above finite simple continued fraction by [x0 : x1, x2, . . . , xn].

Question 7

nth convergent

Answer 7

The nth convergent of [x0 : x1, x2, . . .] is the rational number pn/qn = [x0 : x1, . . . , xn].

Question 8

Periodic Simple Continued Fraction

Answer 8

A periodic simple continued fraction is a simple continued fraction with a repeating block. [x0:x1,x2,…,xk,y1,…,yn] where y1,…,yn repeats infinitely

Question 9

Quadratic Irrational

Answer 9

A quadratic irrational is an irrational real number that is a solution of a quadratic
equation with integer coefficients

Question 10

Purely Periodic

Answer 10

An infinite simple continued fraction of the form [x0:x1,…,xn] is called purely periodic if it repeats x0,….xn

Question 11

Conjugate

Answer 11

Let α = r + s√d be a quadratic irrational. We define the conjugate of α as the quadratic irrational α* = r − s√d.

Question 12

Reduced Quadratic Irrational

Answer 12

Let α = r + s√d be a quadratic irrational.

We say that α is a reduced quadratic irrational if α > 1 and −1 < α* < 0

Question 13

Pell Equations

Answer 13

Pell equations are quadratic Diophantine equations of the form x^2 - dy^2 = 1, where d is a positive integer

Question 14

Fundamental Solution

Answer 14

Suppose that x^2 - dy^2 = 1 has non trivial solutions. We define the fundamental solution to be the minimal positive solution (x1, y1)

Question 15

Congruent Modulo n

Answer 15

Let n be a fixed positive integer. We say that integers a and b are congruent modulo n if n divides a-b. We shall write a ≡ b mod n to denote that a and b are congruent modulo n

Question 16

Unit

Answer 16

An element [a] ∈ Zn is called a unit if there exists [b] ∈ Zn satisfying [a][b] = [b][a] = [1].
We write Un to denote the set of all units in Zn.

Question 17

ϕ(n)

Answer 17

Let n be a positive integer. We define ϕ(n) to be the number of positive integers a less than or equal to n with gcd(a, n) = 1.
(Thus ϕ(n) = |Un|.)

Question 18

Primitive Root Modulo n

Answer 18

Let n be a positive integer. An element of [a] ∈ Un is called a primitive root
modulo n if it has order ϕ(n)

Question 19

Quadratic Residue

Answer 19

Let n be a positive integer. An element [a] ∈ Un is called a quadratic residue if
[a] = [x]^2 for some [x] ∈ Un.

Question 20

Quadratic Non Residues

Answer 20

If [a] ∈ Un is not a quadratic residue, then we call it a

quadratic non-residue. We denote the set of quadratic residues by Qn

Question 21

Hensel’s Lemma

Answer 21

Let f(x) be a polynomial with integer coefficients and let p be a prime. Assume that there exists a ∈ Z with;
(1) f(a) ≡ 0 mod p.
(2) f’(a) !≡ 0 mod p
Then for all m ≥ 1 there exists a unique integer r with 1 ≤ r ≤ p^m and
(a) f(r) ≡ 0 mod p^m.
(b) r ≡ a mod p.

Question 22

Euler’s Critierion

Answer 22

Let p be an odd prime and let a ∈ Z. Then

(a/p) ≡ a^(0.5(p-1)) mod p

Question 23

Quadratic Reciprocity Theorem

Answer 23

Let p and q be distinct odd primes. Then

q/p)(p/q) = (-1)^(0.25(p-1)(q-1)

Question 24

Which real numbers have a finite simple continued fraction?

Answer 24

Rationals

Question 25

Which real numbers have a infinite simple continued fraction?

Answer 25

Irrationals

Question 26

Which real numbers have a periodic simple continued fraction expansion?

Answer 26

Quadratic Irrationals

Question 27

State Fermat’s Little Theorem

Answer 27

Let p be a prime and let a be an integer not divisible by p. Then a^(p−1) ≡ 1 mod p

Question 28

State Lagrange’s Polynomial Congruence Theorem

Answer 28

Let f(x) be a polynomial of degree d with integer coefficients and let p be a prime. If some coefficient of f is not divisible by p, then the congruence f(x) ≡ 0modp has at most d solutions modulo p.

Question 29

When is a number purely periodic?

Answer 29

A quadratic irrational is purely periodic iff it is reduced

Question 30

State Wilson’s Theorem

Answer 30

A positive integer p is prime iff (p-1)! ≡ -1 mod p