A composite number has a prime factor at most its square root
Builds on Composite numberSmallest prime factor
Statement
Let be a composite number. Then has a prime factor with , that is, .
Remarks
The smallest prime factor of has this property. Write . Then , and each prime factor of is at least , so and . This result justifies trial division: to test whether is prime, it is enough to test the primes . For example, and none of divides , so is prime.
Reading path
To understand this page from the ground up, read these 6 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Divisibility definition
- Prime number definition
- Composite number definition
- Existence of a prime divisor statement
- Smallest prime factor definition
- A composite number has a prime factor at most its square root statement
Further reading
About this page
| Tag | 0EB6BBMQMC |
|---|---|
| URI | m2://0EB6BBMQMC |
| Kind | statement, proposition |
| Writing | W0 stub |
| MSC | 11A51 |
| Status | This copy of the site has no build data. Run m2 status 0EB6BBMQMC. |
| Uses | Composite number, Smallest prime factor |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.