High School Mathematics Extensions/Primes/Definition Sheet

Definitions 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 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.