Shared Flashcard Set

Details

Number Theory
Final
10
Mathematics
Undergraduate 4
05/31/2010

Additional Mathematics Flashcards

 


 

Cards

Term
Well-Ordering Principle
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
The Division Algorithm
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
Euclid’s Lemma
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
Euclid’s Theorem
Definition
There are infinitely many primes
Term
Fermat’s Theorem
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
Wilson’s Theorem
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

Supporting users have an ad free experience!