HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Division, Divisibility Rules and Primes
  1. 1The division algorithm and divisibility
  2. 2Divisibility rules and why they work
  3. 3Primes and the fundamental theorem
  1. Mathematics
  2. /Division, Divisibility Rules and Primes
  3. /Primes and the fundamental theorem

Course 27.1·Lesson 3 of 3

Primes and the fundamental theorem

A prime is a whole number above 111 whose only positive divisors are 111 and itself. Every whole number above 111 has a prime divisor, a composite number has one that is at most its square root, and there are infinitely many primes. The fundamental theorem of arithmetic says that each number above

Lesson 3 of 3Show all lessonsHide
Division, Divisibility Rules and Primes
  1. 1The division algorithm and divisibility
  2. 2Divisibility rules and why they work
  3. 3Primes and the fundamental theorem

Try the code and the simulations beside the lesson.

What you will be able to do

  • test a number for primes by trial division up to its square root, and use the sieve;
  • prove that there are infinitely many primes;
  • state and prove the fundamental theorem of arithmetic, and use prime factorisations to decide when a number is a square or a cube.

Building blocks

You can build 121212 as 2×62 \times 62×6 or as 3×43 \times 43×4. Keep breaking: 12=2×2×312 = 2 \times 2 \times 312=2×2×3, and the pieces will not break any further. These pieces are the primes.

A prime is an integer p>1p > 1p>1 whose only positive divisors are 111 and ppp. An integer above 111 that is not prime is composite. The number 111 is neither. If 111 were a prime, factorisation would not be unique: 6=2×3=1×2×36 = 2 \times 3 = 1 \times 2 \times 36=2×3=1×2×3.

Every number has a prime divisor

Take n>1n > 1n>1 and let ddd be its smallest divisor above 111. If ddd had a divisor ccc with 1<c<d1 < c < d1<c<d, then ccc would divide nnn and be smaller than ddd. That cannot be. So ddd is prime.

If nnn is composite, write n=abn = abn=ab with 1<a≤b1 < a \le b1<a≤b. Then a2≤ab=na^2 \le ab = na2≤ab=n, so a≤na \le \sqrt{n}a≤n​. A composite number has a prime divisor that is at most its square root. To test nnn, try the primes up to n\sqrt{n}n​. To test 979797, try 222, 333, 555 and 777. None divides it, so 979797 is prime.

The sieve of Eratosthenes lists all primes up to NNN. Write the numbers from 222 to NNN. Circle 222 and cross out its other multiples. Circle the next number left, and cross out its multiples. Stop when you pass N\sqrt{N}N​: the numbers left are prime.

A ten by ten grid of the numbers 1 to 100. The 25 primes up to 100 are in blue squares: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. The other numbers are grey, and the number 1 is crossed out. A note says that only the multiples of 2, 3, 5 and 7 need to be crossed out, because 11 times 11 is already more than 100.

There are infinitely many primes

This proof is about two thousand three hundred years old, and it is in Euclid's Elements.

  1. Suppose there were only finitely many primes, p1,p2,…,pkp_1, p_2, \dots, p_kp1​,p2​,…,pk​.
  2. Form N=p1p2⋯pk+1N = p_1 p_2 \cdots p_k + 1N=p1​p2​⋯pk​+1. It is bigger than 111, so it has a prime divisor ppp.
  3. The prime ppp is one of the pip_ipi​, so ppp divides the product p1⋯pkp_1 \cdots p_kp1​⋯pk​.
  4. Then ppp divides N−p1⋯pk=1N - p_1 \cdots p_k = 1N−p1​⋯pk​=1. No prime divides 111, so the list was not complete.

Be careful. The proof does not say that NNN itself is prime. Indeed 2×3×5×7×11×13+1=30031=59×5092 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 5092×3×5×7×11×13+1=30031=59×509.

Primes can also be far apart. The numbers n!+2,n!+3,…,n!+nn! + 2, n! + 3, \dots, n! + nn!+2,n!+3,…,n!+n are n−1n - 1n−1 composite numbers in a row, because k∣n!+kk \mid n! + kk∣n!+k for 2≤k≤n2 \le k \le n2≤k≤n.

Euclid's lemma

Euclid's lemma. If a prime ppp divides a product ababab, then p∣ap \mid ap∣a or p∣bp \mid bp∣b.

This is the special property of primes. It fails for 666, as lesson 1 showed. We prove it in course 2 with Bezout's identity. By repeating it, if ppp divides a product of many factors, it divides one of them.

The fundamental theorem of arithmetic

Theorem. Every integer n>1n > 1n>1 can be written as a product of primes, and the product is unique apart from the order of the factors.

Existence. Suppose some numbers have no factorisation, and let nnn be the smallest. It is not prime, so n=abn = abn=ab with 1<a,b<n1 < a, b < n1<a,b<n. Both aaa and bbb are smaller than nnn, so both have factorisations. Joining them gives one for nnn, which is impossible.

Uniqueness. Suppose p1p2⋯pr=q1q2⋯qsp_1 p_2 \cdots p_r = q_1 q_2 \cdots q_sp1​p2​⋯pr​=q1​q2​⋯qs​, all primes. The prime p1p_1p1​ divides the right side, so by Euclid's lemma it divides some qjq_jqj​. A prime that divides a prime is equal to it, so p1=qjp_1 = q_jp1​=qj​. Cancel it from both sides and repeat. The two lists hold the same primes, the same number of times.

We write the factorisation with exponents, n=p1a1p2a2⋯pkakn = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}n=p1a1​​p2a2​​⋯pkak​​. For example 360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5360=23⋅32⋅5. This is the canonical form. School books in India call it the prime factorisation, and some books say "standard form".

Squares, cubes and powers

The theorem lets us read properties straight from the exponents.

  • nnn is a perfect square exactly when every exponent is even. 360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5360=23⋅32⋅5 is not, and 360×10=24⋅32⋅52=602360 \times 10 = 2^4 \cdot 3^2 \cdot 5^2 = 60^2360×10=24⋅32⋅52=602 is.
  • nnn is a perfect kkkth power exactly when every exponent is a multiple of kkk.
  • If ababab is a perfect square and aaa and bbb share no prime, then aaa and bbb are both perfect squares. Each prime of ababab sits wholly inside aaa or wholly inside bbb, with its even exponent.

Primes above 3. Every prime p>3p > 3p>3 leaves remainder 111 or 555 on division by 666, since the other remainders give a multiple of 222 or 333. So p=6k±1p = 6k \pm 1p=6k±1, and p2−1=(p−1)(p+1)p^2 - 1 = (p - 1)(p + 1)p2−1=(p−1)(p+1) is a multiple of 242424.

Practise with new numbers

Try it in Python

The program runs the sieve, counts the primes up to 100010001000, and factorises Euclid's numbers 2×3×⋯×p+12 \times 3 \times \dots \times p + 12×3×⋯×p+1.

Read it first. Then run it. Which of Euclid's numbers are prime, and which are not?

1. Change primes_up_to(1000) to primes_up_to(10000). How many primes are there now?

2. Use factorise on n2+n+41n^2 + n + 41n2+n+41 for n=40n = 40n=40 and n=41n = 41n=41. What do you see?

Common mistakes

  • Calling 1 a prime. It is not. The first prime is 222, the only even prime.
  • Testing divisors past the square root. You only need the primes up to n\sqrt{n}n​.
  • Thinking that p1⋯pk+1p_1 \cdots p_k + 1p1​⋯pk​+1 is always prime. It has a new prime factor, which may be a smaller number than itself.
  • Trusting a pattern. n2+n+41n^2 + n + 41n2+n+41 is prime for n=0n = 0n=0 to 393939, and 402+40+41=41240^2 + 40 + 41 = 41^2402+40+41=412.

Remember these

  • A composite nnn has a prime factor at most n\sqrt{n}n​.
  • There are infinitely many primes (Euclid).
  • Euclid's lemma: if p∣abp \mid abp∣ab, then p∣ap \mid ap∣a or p∣bp \mid bp∣b.
  • Every n>1n > 1n>1 is a product of primes in exactly one way.
  • nnn is a perfect kkkth power when every exponent in its factorisation is a multiple of kkk.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Is 221221221 prime? Which primes do you need to try?
  1. Write 118811881188 in canonical form.
  1. Find the smallest whole number kkk for which 1188k1188k1188k is a perfect cube.
  1. Give a run of five consecutive composite numbers.
  1. Explain why p2−1p^2 - 1p2−1 is divisible by 242424 for every prime p>3p > 3p>3.

References

  • David M. Burton, Elementary Number Theory, Chapter 3, sections 3.1 to 3.3 on the fundamental theorem, the sieve and the infinitude of primes.
  • NCERT, Mathematics Textbook for Class X, Chapter 1 (Real Numbers), for the fundamental theorem of arithmetic.

Enroll free in Division, Divisibility Rules and Primes

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (4)

Every odd prime leaves remainder 1 or 3 on division by 4…Advanced · High School (11–12) · by StemPy Lab
A student computes n⁴ + 4 for small n: 5, 20, 85, 260…Advanced · High School (11–12) · by StemPy Lab
We want positive whole numbers n with special multiples…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Division, Divisibility Rules and Primes
← Divisibility rules and why they workNext →

Discussion (0)

Log in to join the discussion.

Loading…

111
is a product of primes in exactly one way, apart from the order.
about 30 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Numbers of the form 2ⁿ - 1 are called Mersenne numbers…
Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Prime factorisation machinePython Lab · by StemPy Lab

Question Sets (1)

Division and Primes: Check Your Understanding10 questions · by StemPy Lab

Notes (1)

Division, Divisibility Rules and Primes: Quick RevisionNote · by StemPy Lab