# STEP I-2009-1

A proper factor of an integer N is a positive integer, not 1 or N, that divides N.

Show that $3^2 \times 5^3$ has exactly 10 proper factors. Determine how many other integers of the form $3^m \times 5^n$ (where m and n are integers) have exactly 10 proper factors.

Let N be the smallest positive integer that has exactly 426 proper factors. Determine N, giving your answer in terms of its prime factors. Continue reading

# STEP III/2015/5

In the following argument to show that √2 is irrational, give proofs appropriate for steps 3, 5 and 6.

1. Assume that √2 is rational.

2. Define the set S to be the set of positive integers with the following property:

n is in S if and only if n√2 is an integer.

3. Show that the set S contains at least one positive integer.

4. Define the integer k to be the smallest positive integer in S

5. Show that (√2-1)k is in S.

6. Show that steps 4 and 5 are contradictory and hence that √2 is irrational.

Prove that $2^\frac{1}{3}$ is rational if and only if $2^\frac{2}{3}$ is rational.

Use an argument similar to that of part (i) to prove that $2^\frac{1}{3}$ and $2^\frac{2}{3}$ are irrational.

Click here for solution by Yuliia Tereshchuk

# STEP II/2005/2

For any positive integer N, the function f(N) is defined by

$f(N) = N\Big(1-\frac1{p_1}\Big)\Big(1-\frac1{p_2}\Big) \cdots\Big(1-\frac1{p_k}\Big)$

where $p_1, p_2, \dots , p_k$ are the only prime numbers that are factors of N.

Thus $f(80)=80(1-\frac{1}{2})(1-\frac{1}{5})\,$

(1) Evaluate f(12) and f(180)

(2) Show that f(N) is an integer for all N

(3) Prove, or disprove by means of a counterexample, each of the following:

(a) $f(m) f(n) = f(mn)$

(b) $f(p) f(q) = f(pq)$ if p and q are distinct prime numbers;

(c) $f(p) f(q) = f(pq)$ only if p and q are distinct prime numbers.

(4) Find a positive integer m and a prime number p such that

$f(p^m) = 146410$

# STEP II/2018/6

(i) Find all pairs of positive integers (n,p), where p is a prime number, that satisfy

$n!+ 5 = p$

(ii) In this part of the question you may use the following two theorems:

For $n\ge 7, 1! \times 3! \times \cdots \times (2n-1)! > (4n)!\,$

For every positive integer n, there is a prime number between 2n and 4n.

Find all pairs of positive integers (n,m) that satisfy

$1! \times 3! \times \cdots \times (2n-1)! = m!$

Click here for a solution