Math 2.0

Number theory Proposition

A composite number has a prime factor at most its square root

Builds on Composite numberSmallest prime factor

Statement

Let nn be a composite number. Then nn has a prime factor pp with p2≤np^2 \le n, that is, p≤np \le \sqrt{n}.

Remarks

The smallest prime factor pp of nn has this property. Write n=pmn = p m. Then m>1m > 1, and each prime factor of mm is at least pp, so m≥pm \ge p and n≥p2n \ge p^2. This result justifies trial division: to test whether n>1n > 1 is prime, it is enough to test the primes p≤np \le \sqrt{n}. For example, 97<10\sqrt{97} < 10 and none of 2,3,5,72, 3, 5, 7 divides 9797, so 9797 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
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Prime number definition
  3. Composite number definition
  4. Existence of a prime divisor statement
  5. Smallest prime factor definition
  6. A composite number has a prime factor at most its square root statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Trial_division, Method
About this page
Tag0EB6BBMQMC
URIm2://0EB6BBMQMC
Kindstatement, proposition
WritingW0 stub
MSC11A51
StatusThis copy of the site has no build data. Run m2 status 0EB6BBMQMC.
UsesComposite 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.