Category Archives: Number theory, combinatorics

STEP II/1996/3

The Fibonacci numbers Fn are defined by the conditions: F0=0, F1=1, and Fn+1 = Fn + Fn-1 for all n ≥ 1. Show that F2=1, F3=2, F4=3, and compute F5, F6 and F7.

Compute Fn+1Fn-1 − F02 for a few values of n; guess a general formula and prove it by induction, or otherwise.

By induction on k, or otherwise, show that Fn+k=FkFn+1+Fk-1Fn for all positive integers n and k.

Click here for a solution

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

Continue reading →