High School Mathematics Extensions/Primes/Definition Sheet
Jump to navigation
Jump to search
HSME |
Content |
---|
Primes |
Modular Arithmetic |
Problems & Projects |
Problem Set |
Project |
Solutions |
Exercise Solutions |
Problem Set Solutions |
Misc. |
Definition Sheet |
Full Version |
PDF Version |
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]
Composite
- A composite is a whole number that is not a prime. The number 1 is not composite.
Coprimes
- 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.
Factorisation
- 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.
Inverse
- 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.
Modular arithmetic
- 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.
Prime
- 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]
Chinese Remainder Theoren
In a system of n congruencies
- ...
, a solution exists if and only if for i and j with i ≠ j
- gcd(m_{i},m_{j}) divides (a_{i} - a_{j})
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.