What is Prime number? — Mathematics

Definition 64.5 Primary & Middle School Mathematics · Chapter 64 — Arithmetic: Divisors and Prime Numbers

A prime number is an integer $\geq 2$ whose only divisors are $1$ and itself. The primes below $30$ are

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

The number $1$ is not prime (by convention), and an integer $\geq 2$ that is not prime is called composite.

The factor tree of 360: each step splits off the smallest prime factor (in red). Reading the red leaves and the final 5: 360 = 23 × 32 × 5. — The factor tree of $360$ : each step splits off the smallest prime factor (in red). Reading the red leaves and the final $5$ : $360 = 2^3 \times 3^2 \times 5$ .

Read in context →

Definition 6.12 University Mathematics — Year 1 · Chapter 6 — Integer Arithmetic

An integer $p \geq 2$ is prime when its only positive divisors are $1$ and $p$ . For $p$ prime and $a \in \Z$ : either $p \mid a$ , or $\gcd(p, a) = 1$ . Consequently (Theorem 6.8), Euclid’s lemma holds: if $p \mid ab$ then $p \mid a$ or $p \mid b$ .

Examples

Example 6.24 (Fermat’s converse fails: $341$ )

Fermat’s little theorem gives a cheap compositeness test: if $a^{n-1} \not\equiv 1 \pmod n$ for some $a$ coprime to $n$ , then $n$ is not prime. Could the test also certify primality? No: take $n = 341 = 11 \times 31$ , composite, and $a = 2$ . Since $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

the composite $341$ passes Fermat’s test for the base $2$ (it is the smallest such pseudoprime). The base $3$ unmasks it ( $3^{340} \not\equiv 1$ ), and practical primality testing therefore runs the test on several bases, plus refinements — the industrial versions of this idea are what certify the large primes of Remark 6.27. Moral: an implication and its converse live separate lives (Remark 1.10), even for theorems.

Read in context →

Examples

Related terms