Number Theory Definitions

Question 1

Definition of Prime

Answer 1

a positive integer p is prime iff the only positive integers dividing p are 1 and p.

Question 2

Definition of Composite

Answer 2

a positive integer n is composite iff there exist integers a,b with 1 < a, b < n such that n = ab

Question 3

gcd(a, b)

Answer 3

gcd(a,b) = d such that d is the largest possible integer such that d|a and d|b.

Question 4

lcm(a, b)

Answer 4

lcm(a,b) = l such that l is the smallest possible integer such that a|l and b|l.

Question 5

gcd(a, b) (prime factorization)

Answer 5

p1^min(e_1a, e_1b) * p2^min(e_2a, e_2b) * …

Question 6

lcm(a, b) (prime factorization)

Answer 6

p1 ^ max(e_1a, e_1b) * p2 ^ max(e_2a, 2b) …

Question 7

lcm(a,b) * gcd(a, b) =

Answer 7

ab

Question 8

Division Algorithm

Answer 8

For all integers a, b such that b is not 0, there exist unique integers q and r such that a = qb + r and 0 < r < |b|

Question 9

1 + r + r^2 + … + r^n

Answer 9

(r^{n+1} - 1) / (r - 1)

Question 10

Formula for number of digits (base 10) for natural number n

Answer 10

k = floor(log(n)) + 1

Question 11

Number of digits (base b) for natural number n

Answer 11

k = floor(log_b(n)) + 1

Question 12

Log_b(n) (in terms of log_10)

Answer 12

[log_10(n)] / [log_10(b)]

Question 13

Definition of divisibility

Answer 13

a|b iff (if and only if) there exists an integer k such that b = ka

Question 14

Divisibility tautologies

Answer 14

a|a, 1|a, a|0

Question 15

if a|b and a|c, then ??? (integer linear combination)

Answer 15

a|(bx + cy) where x, y are integers

Question 16

Fundamental Theorem of Arithmetic (Unique Factorization Theorem)

Answer 16

Every integer n > 1 can be written uniquely (up to ordering) as a product of primes. In other words, for all integers n, n > 1, n = p_1^(e1) p_2^(e2)…p_k^(ek) for distinct primes p_1, …, p_k. The primes and exponents (ei) are unique with ei > 0.

Question 17

Consequence of Fundamental Theorem of Arithmetic

Answer 17

for every integer n > 1, there exists a prime such that p|n.

Question 18

Definition of a rational number

Answer 18

A number n is rational iff there exist integers a, b with b \ne 0 st. n = a/b