High School Mathematics Extensions/Primes/Definition Sheet

From Wikibooks, open books for an open world
< High School Mathematics Extensions‎ | Primes
Jump to: navigation, search
HSME
Content
100% developed Primes
100% developed Modular Arithmetic
Problems & Projects
100% developed Problem Set
100% developed Project
Solutions
100% developed Exercise Solutions
50% developed Problem Set Solutions
Misc.
100% developed Definition Sheet
100% developed Full Version
25% developed PDF Version
High School Mathematics Extensions75% developed

Supplementary Chapters50% developedPrimes and Modular Arithmetic100% developedLogic75% developed

Mathematical Proofs75% developedSet Theory and Infinite Processes50% developed Counting and Generating Functions75% developedDiscrete Probability25% developed

Matrices100% developedFurther Modular Arithmetic50% developedMathematical Programming0% developed

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

Inverse

In modular m arithmetic, the inverse of a is the number b such that
ab \equiv 1 \pmod{m} \!
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

x \equiv a_1 \pmod{ m_1}\,\!
x \equiv a_2 \pmod{ m_2}\,\!
...
x \equiv a_n \pmod{ m_n}\,\!

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