Express a number in prime-factor index form

Whole number

\(\displaystyle 36\)

Which is a complete prime factorisation of 36 in index form?

Change the whole number. Each branch splits a number into two factors. At 72, the first split is 8 × 9; both factors are composite, so both are split further

When is a factor tree complete?

Two methods, the same prime factors

A factor tree may begin with any pair of factors greater than 1. Split every composite factor further. Alternatively, divide repeatedly by primes until the quotient is 1. In both methods, group repeated primes as powers and check their product

1. 1Primes only at the end A composite factor is a valid intermediate step, but not a finished prime factorisation
2. 2Count copies, not branches An index counts occurrences of that prime across all leaves
3. 3Order does not change the product The prime powers may be written in any order. A prime used once may be written without its index 1.

Current factors

\(\displaystyle 360=8\times45\)

A tree for 360 has reached 8 × 45. What should happen next?

Select the first incorrect line

What makes a number prime?

A positive divisor divides a number with no remainder. A prime has exactly two positive divisors. A composite integer greater than 1 has an additional positive divisor. The number 1 has only one positive divisor, so it is neither prime nor composite

1. 1Primes start above one A prime is an integer greater than 1 with exactly two positive divisors: 1 and itself. A composite integer is greater than 1 and is not prime. The number 1 is neither

Why is 1 excluded from the prime numbers?

The fundamental theorem of arithmetic

Every integer n greater than 1 can be written as a finite product of primes, uniquely apart from the order of the factors. Grouping equal primes gives positive integer exponents on distinct prime bases. Different factor-tree starting points cannot change those final primes or their multiplicities. We use this theorem here; a full formal uniqueness proof is not part of this lesson

1. 1Existence and uniqueness Every integer greater than 1 has a factorisation into primes. Apart from the order of the factors, that factorisation is unique. After equal primes are grouped, both the prime bases and their positive exponents are fixed \(\displaystyle 198=2\times3^2\times11\)

Two complete prime factorisations of the same positive integer list the prime powers in different orders. What does uniqueness tell us?

Why a prime divisor always exists

Let n be an integer greater than 1. It has at least one divisor greater than 1, namely n itself. Choose the smallest such divisor d. If d were composite, it would have a factor a greater than 1 and less than d. Since a divides d and d divides n, a would be a smaller divisor of n greater than 1, a contradiction. Therefore d is prime. This establishes the existence needed below without using an induction argument

Test the construction on a finite collection

Start with the prime collection 2, 5 and 11. This is a finite collection, not a claim to list all primes. Multiply its entries and add 1. The result is not divisible by any prime in the collection. It may be composite; what matters is that it has a prime divisor outside the collection

1. 1Make a number missed by a finite list Multiply the primes in the list and add 1. Dividing this new number by any listed prime leaves remainder 1. \(\displaystyle \begin{gathered}P=p_1p_2\cdots p_r\\N=P+1\end{gathered}\)

Construction

\(\displaystyle N=2\times5\times11+1\)

Calculate the number formed by multiplying the three listed primes and adding 1.

Construction

\(\displaystyle 111=2\times5\times11+1\)

Factorisation

\(\displaystyle 111=3\times37\)

The constructed number is composite. Does this defeat the argument?

From an example to an arbitrary finite list

To prove infinitude by contradiction, assume the opposite: all primes form a finite list p₁, …, pᵣ. There is at least one prime, since 2 is prime. Let P be their product and N = P + 1. Then N is an integer greater than 1. Every listed prime divides P, so N leaves remainder 1 on division by each listed prime. No listed prime divides N.

Construction

\(\displaystyle N=P+1,\quad p>1\)

A listed prime p divides P exactly. What remainder does N leave when divided by p?

Supposed complete list

\(\displaystyle P=p_1p_2\cdots p_r,\quad N=P+1\)

Which step turns the constructed number into a contradiction of the supposed complete prime list?

A proposed proof says: “The product of all listed primes plus 1 is prime, so the list is incomplete.” What is the unsupported claim?

Written proof practice, ungraded

On paper, prove that there are infinitely many primes. State the finite-list assumption, construct an integer greater than 1, justify why it has a prime divisor, exclude every listed prime as a divisor and state the contradiction. Do not assume the constructed integer is prime. This full proof is not automatically marked

Model proof: assumption and construction

Suppose, for a contradiction, that there are only finitely many primes, listed as p₁, …, pᵣ. The list is nonempty because 2 is prime. Form their product P and let N = P + 1. Since N is an integer greater than 1, it has a prime divisor q. This existence follows, for example, by taking the smallest divisor of N greater than 1 and showing it is prime

Model proof: contradiction and conclusion

Suppose a finite list contains every prime. Let P be the product of its entries, N that product plus 1, and q a prime divisor of N. For each listed prime pᵢ, we have pᵢ dividing P. If pᵢ also divided N, it would divide N − P = 1, which is impossible because pᵢ > 1. Thus q is absent from the list. This contradicts the assumption that the list contains every prime. Therefore there are infinitely many prime numbers

Check the reasoning, not just the answer

A complete proof needs an arbitrary supposed complete finite list, not one numerical example. It must establish the existence of a prime divisor and explain why every listed prime is excluded. Finally, name the contradiction and conclude infinitude. The objective checks in this lesson test selected steps only; they do not establish that you can produce this written argument independently

1. 1Finish the contradiction A prime divisor of N cannot be any listed prime. A finite list therefore cannot contain every prime. This proves there are infinitely many primes, not merely that one computed example is large