Term
|
Definition
| Every nonempty set S of nonnegative integers contains a least element; that is, there is some integer a in S such that a≤b for all b's in S |
|
|
Term
| First Principle of Finite Induction |
|
Definition
Let S be a set of positive integers with the following properties:
(a) 1 is in S
(b) If k is in S , then k + 1 is in S.
Then S is the set of all positive integers |
|
|
Term
| Second Principle of Finite Induction |
|
Definition
Let S be a set of positive integers with the following properties:
(a) 1 is in S
(b) If k is a positive integer such that 1, 2, . . . , k are in S , then k +1 is S.
Then S is the set of all positive integers |
|
|
Term
|
Definition
Given integers a and b, with b > 0, there exist unique integers q and r satisfying a = qb + r and 0 ≤ r < b. The integers q and r are called, respectively,
the quotient and the remainder |
|
|
Term
|
Definition
If a l bc, with gcd(a,b) = 1, then a l c
Proof:
since the gcd(a,b)=1, 1=ax+by for x,y in Z
so c=(ax+by)c=acx+bcy
since a l ac and a l bc, a l (acx + bcy)
so a l c(ax+by). Therefore a l c |
|
|
Term
| Fundamental Theorem of Arithmetic |
|
Definition
| Every positive integer n > 1 can be expressed as a product of primes; this representation is unique, apart from the order in which the factors appear. |
|
|
Term
|
Definition
| There are infinitely many primes |
|
|
Term
|
Definition
Let p be a prime and suppose that p does not divide a. Then ap-1 ≡ 1 (mod p)
Corollary:
If p is a prime, then ap ≡ a (mod p) for any integer a. |
|
|
Term
|
Definition
| If p is a prime, then (p-1)! ≡ -1 (mod p) |
|
|
Term
| Chinese Remainder Theorem |
|
Definition
Let n1, ..., nr be positive integers such that gcd(ni,nj)=1 for i≠j. The system of congruence
x ≡ a1 (mod n1)
.
.
.
x ≡ ar (mod nr)
has a simultaneous solution, which is unique modulo n = n1n2 . . . nr |
|
|
