# Category Archives: Number theory, combinatorics

# STEP I/2014/1

# Using a fixed-point theorem from group theory to prove other results

# STEP I-2009-1

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

Show that has exactly 10 proper factors. Determine how many other integers of the form (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 is rational if and only if is rational.

Use an argument similar to that of part (i) to prove that and are irrational.

# STEP II/2005/2

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

where are the only prime numbers that are factors of N.

Thus

(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)

(b) if p and q are distinct prime numbers;

(c) only if p and q are distinct prime numbers.

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

# STEP II/2018/6

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

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

For

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

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