Basic Algebra B.1 Number Theory Basics

Question 1

divides and divisor

Answer 1

Definition. If a and b, b != 0, are integers and if a = kb for some integer k, then we say that b divides a and that b is a divisor of a. We write b|a.

Question 2

prime number, relatively prime number, greatest common divisor and least common multiple

Answer 2

Definition. A positive integer p greater than 1 whose only integer divisors are ±1 or ±p is called a prime number. Two integers a and b are said to be relatively prime if ±1 are the only common divisors. Given nonzero integers n1, n2,…, nk, the greatest common divisor of these integers, denoted by gcd(n1,n2,…,nk) or simply (n1,n2) if k = 2, is the largest integer that divides all the ni. The least common multiple of these integers, denoted by lcm(n1,n2,…,nk), is defined to be the smallest nonnegative integer m so that ni divides m for all i.

Question 3

greatest common divisor theorem

Answer 3

B.1.1. Theorem. If a and b are integers that have a greatest common divisor d, then there are integers s and t such that sa + tb = d.

Question 4

congruent modulo m

Answer 4

Definition. Let m be an integer. Two integers a and b are said to congruent modulo m, or mod m, if m divides a - b, equivalently, a = b + km for some k. In that case we shall write a = b mod(m).

Question 5

quadratic residue modulo m

Answer 5

Definition. Let a and m be integers. If (a,m) = 1, then a is called a quadratic residue modulo m if the congruence x^2 = a mod(m) has a solution; otherwise, a is called a quadratic nonresidue modulo m.