# 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 |

## Contents |

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