High School Mathematics Extensions/Primes/Definition Sheet
|Problems & Projects|
|Problem Set Solutions|
About the definition sheet:
The definitions provided below may differ a little from the ones given in the chapter. If possible, print out the following definitions for easy reference.
Definitions[edit | edit source]
- A composite is a whole number that is not a prime. The number 1 is not composite.
- Two numbers are coprimes if their greatest common divisor (gcd) equals 1.
Diophantine Equation (linear)
- An equation of the form ax + by = c. Where a, b and c are integer constants, and x and y are unknown integers.
- Alternatively spelt factorization. A process in which the prime factors of a natural number are found and the number expressed as the product of the individual factors.
gcd (greatest common divisor)
- The gcd of a and b is a number d, such that d divides a and d divides b; and that if e divides a and b, then e ≤ d.
- In modular m arithmetic, the inverse of a is the number b such that
- the inverse is unique. Not every number in every arithmetic have an inverse.
- The arithmetic modulo m is the arithmetic where each number is represent by a number lying between 0 and m - 1. E.g. consider modulo 7 arithmetic, 11 is represented by 4; and -2 is represented by 5. We say 11 is equivalent to 4 mod 7; and -2 is equivalent to 5 mod 7. It is explained in more detail here.
- A prime number (or prime for short) is a whole number that can only be wholly divided by two different numbers, 1 and itself. The number 1 is thus not considered prime. We do not consider the negative numbers in this chapter.
Theorems[edit | edit source]
Chinese Remainder Theoren
In a system of n congruencies
, a solution exists if and only if for i and j with i ≠ j
- gcd(mi,mj) divides (ai - aj)
Existence of inverse
- In modular m arithmetic, a has an inverse if and only if gcd(a,m) = 1.
Fundamental Theorem of Arithmetic
- Any integer (except for 1) can be expressed as the product of primes in one and only one way.
Infinitely many primes
- There are infinitely many primes.