Numbers And Sets
Jump to year
Paper 4 , Section I, E
commentConsider functions and . Which of the following statements are always true, and which can be false? Give proofs or counterexamples as appropriate.
(i) If is surjective then is surjective.
(ii) If is injective then is injective.
(iii) If is injective then is injective.
If and with , and is the identity on , then how many possibilities are there for the pair of functions and ?
Paper 4, Section I,
commentThe Fibonacci numbers are defined by . Let be the ratio of successive Fibonacci numbers.
(i) Show that . Hence prove by induction that
for all . Deduce that the sequence is monotonically decreasing.
(ii) Prove that
for all . Hence show that as .
(iii) Explain without detailed justification why the sequence has a limit.
Paper 4, Section II,
comment(a) (i) By considering Euclid's algorithm, show that the highest common factor of two positive integers and can be written in the form for suitable integers and . Find an integer solution of
Is your solution unique?
(ii) Suppose that and are coprime. Show that the simultaneous congruences
have the same set of solutions as for some . Hence solve (i.e. find all solutions of) the simultaneous congruences
(b) State the inclusion-exclusion principle.
For integers , denote by the number of ordered r-tuples of integers satisfying for and such that the greatest common divisor of is 1 . Show that
where the product is over all prime numbers dividing .
Paper 4, Section II,
comment(a) Prove that every real number can be written in the form where is a strictly increasing sequence of positive integers.
Are such expressions unique?
(b) Let be a root of , where . Suppose that has no rational roots, except possibly .
(i) Show that if then
where is a constant depending only on .
(ii) Deduce that if with and then
(c) Prove that is transcendental.
(d) Let and be transcendental numbers. What of the following statements are always true and which can be false? Briefly justify your answers.
(i) is transcendental.
(ii) is transcendental for every .
Paper 4, Section II, 8E
comment(a) Prove that a countable union of countable sets is countable.
(b) (i) Show that the set of all functions is uncountable.
(ii) Determine the countability or otherwise of each of the two sets
Justify your answers.
(c) A permutation of the natural numbers is a mapping that is bijective. Determine the countability or otherwise of each of the two sets and of permutations, justifying your answers:
(i) is the set of all permutations of such that for all sufficiently large .
(ii) is the set all permutations of such that
for each .
Paper 4, Section II, E
comment(a) Let be the set of all functions . Define by
(i) Define the binomial coefficient for . Setting when , prove from your definition that if then .
(ii) Show that if is integer-valued and , then
for some integers .
(b) State the binomial theorem. Show that
Paper 2, Section I,
commentDefine an equivalence relation. Which of the following is an equivalence relation on the set of non-zero complex numbers? Justify your answers. (i) if . (ii) if . (iii) if is rational for some integer . (iv) if .
Paper 2, Section II, D
comment(a) Define what it means for a set to be countable. Prove that is countable, and that the power set of is uncountable.
(b) Let be a bijection. Show that if and are related by then they have the same number of fixed points.
[A fixed point of is an element such that .]
(c) Let be the set of bijections with the property that no iterate of has a fixed point.
[The iterate of is the map obtained by successive applications of .]
(i) Write down an explicit element of .
(ii) Determine whether is countable or uncountable.
Paper 2, Section II, D
comment(a) Define the Euler function . State the Chinese remainder theorem, and use it to derive a formula for when is a product of distinct primes. Show that there are at least ten odd numbers with a power of 2 .
(b) State and prove the Fermat-Euler theorem.
(c) In the RSA cryptosystem a message is encrypted as . Explain how and should be chosen, and how (given a factorisation of ) to compute the decryption exponent . Prove that your choice of works, subject to reasonable assumptions on . If and then what is ?
Paper 4, Section , E
commentShow that the series
converge. Determine in each case whether the limit is a rational number. Justify your answers.
Paper 4, Section I, E
commentFind all solutions to the simultaneous congruences
Paper 4, Section II,
comment(a) Let be a function. Show that the following statements are equivalent.
(i) is injective.
(ii) For every subset we have .
(iii) For every pair of subsets we have .
(b) Let be an injection. Show that for some subsets such that
[Here denotes the -fold composite of with itself.]
Paper 4, Section II, E
comment(a) What is a countable set? Let be sets with countable. Show that if is an injection then is countable. Deduce that and are countable. Show too that a countable union of countable sets is countable.
(b) Show that, in the plane, any collection of pairwise disjoint circles with rational radius is countable.
(c) A lollipop is any subset of the plane obtained by translating, rotating and scaling (by any factor ) the set
What happens if in part (b) we replace 'circles with rational radius' by 'lollipops'?
Paper 4, Section II, E
commentState the inclusion-exclusion principle.
Let be an integer. Let and
where is the largest number dividing all of . Let be the relation on where if .
(a) Show that
where the product is over all primes dividing .
(b) Show that if then there exist integers with .
(c) Show that if then there exists an integer with and . [Hint: Consider , where are as in part (b).] Deduce that is an equivalence relation.
(d) What is the size of the equivalence class containing Show that all equivalence classes have the same size, and deduce that the number of equivalence classes is
Paper 4, Section II, E
comment(a) State and prove Fermat's theorem. Use it to compute .
(b) The Fibonacci numbers are defined by , and for all . Prove by induction that for all we have
(c) Let and let be an odd prime dividing . Which of the following statements are true, and which can be false? Justify your answers.
(i) If is odd then .
(ii) If is even then .
Paper 4, Section I, E
commentGiven , show that is either an integer or irrational.
Let and be irrational numbers and be rational. Which of and must be irrational? Justify your answers. [Hint: For the last part consider .]
Paper 4, Section I, E
commentState Fermat's theorem.
Let be a prime such that . Prove that there is no solution to
Show that there are infinitely many primes congruent to .
Paper 4, Section II,
commentLet be a positive integer. Show that for any coprime to , there is a unique such that . Show also that if and are integers coprime to , then is also coprime to . [Any version of Bezout's theorem may be used without proof provided it is clearly stated.]
State and prove Wilson's theorem.
Let be a positive integer and be a prime. Show that the exponent of in the prime factorisation of ! is given by where denotes the integer part of .
Evaluate and
Let be a prime and . Let be the exponent of in the prime factorisation of . Find the exponent of in the prime factorisation of , in terms of and .
Paper 4, Section II,
commentLet and be subsets of a finite set . Let . Show that if belongs to for exactly values of , then
where with the convention that , and denotes the indicator function of Hint: Set and consider for which one has .]
Use this to show that the number of elements of that belong to for exactly values of is
Deduce the Inclusion-Exclusion Principle.
Using the Inclusion-Exclusion Principle, prove a formula for the Euler totient function in terms of the distinct prime factors of .
A Carmichael number is a composite number such that for every integer coprime to . Show that if is the product of distinct primes satisfying for , then is a Carmichael number.
Paper 4, Section II, 8E
commentDefine what it means for a set to be countable.
Show that for any set , there is no surjection from onto the power set . Deduce that the set of all infinite sequences is uncountable.
Let be the set of sequences of subsets of such that for all and . Let consist of all members of for which for all but finitely many . Let consist of all members of for which for all but finitely many . For each of and determine whether it is countable or uncountable. Justify your answers.
Paper 4, Section II, E
commentFor let denote the set of all sequences of length . We define the distance between two elements and of to be the number of coordinates in which they differ. Show that for all .
For and let . Show that .
A subset of is called a -code if for all with . Let be the maximum possible value of for a -code in . Show that
Find , carefully justifying your answer.
Paper 4, Section I, D
comment(a) Give the definitions of relation and equivalence relation on a set .
(b) Let be the set of ordered pairs where is a non-empty subset of and . Let be the relation on defined by requiring if the following two conditions hold:
(i) is finite and
(ii) there is a finite set such that for all .
Show that is an equivalence relation on .
Paper 4, Section I, D
comment(a) Show that for all positive integers and , either or .
(b) If the positive integers satisfy , show that at least one of and must be divisible by 3 . Can both and be odd?
Paper 4, Section II, 7D
comment(a) For positive integers with , show that
giving an explicit formula for . [You may wish to consider the expansion of
(b) For a function and each integer , the function is defined by
For any integer let . Show that and for all and .
Show that for each integer and each ,
Deduce that for each integer ,
Paper 4, Section II, D
commentLet be a sequence of real numbers.
(a) Define what it means for to converge. Define what it means for the series to converge.
Show that if converges, then converges to 0 .
If converges to , show that
(b) Suppose for every . Let and .
Show that does not converge.
Give an example of a sequence with and for every such that converges.
If converges, show that .
Paper 4, Section II, D
comment(a) Define what it means for a set to be countable.
(b) Let be an infinite subset of the set of natural numbers . Prove that there is a bijection .
(c) Let be the set of natural numbers whose decimal representation ends with exactly zeros. For example, and . By applying the result of part (b) with , construct a bijection . Deduce that the set of rationals is countable.
(d) Let be an infinite set of positive real numbers. If every sequence of distinct elements with for each has the property that
prove that is countable.
[You may assume without proof that a countable union of countable sets is countable.]
Paper 4, Section II, D
comment(a) State and prove the Fermat-Euler Theorem. Deduce Fermat's Little Theorem. State Wilson's Theorem.
(b) Let be an odd prime. Prove that is solvable if and only if .
(c) Let be prime. If and are non-negative integers with , prove that
Paper 4, Section I, E
commentExplain the meaning of the phrase least upper bound; state the least upper bound property of the real numbers. Use the least upper bound property to show that a bounded, increasing sequence of real numbers converges.
Suppose that and that for all . If converges, show that converges.
Paper 4, Section I, E
commentFind a pair of integers and satisfying . What is the smallest positive integer congruent to modulo 29 ?
Paper 4, Section II,
commentSuppose that and that , where and are relatively prime and greater than 1. Show that there exist unique integers such that and
Now let be the prime factorization of . Deduce that can be written uniquely in the form
where and . Express in this form.
Paper 4, Section II,
commentState the inclusion-exclusion principle.
Let be a string of digits, where . We say that the string has a run of length if there is some such that either for all or for all . For example, the strings
all have runs of length 3 (underlined), but no run in has length . How many strings of length 6 have a run of length ?
Paper 4, Section II, 8E
commentDefine the binomial coefficient . Prove directly from your definition that
for any complex number .
(a) Using this formula, or otherwise, show that
(b) By differentiating, or otherwise, evaluate .
Let , where is a non-negative integer. Show that for . Evaluate .
Paper 4, Section II, E
comment(a) Let be a set. Show that there is no bijective map from to the power set of . Let for all be the set of sequences with entries in Show that is uncountable.
(b) Let be a finite set with more than one element, and let be a countably infinite set. Determine whether each of the following sets is countable. Justify your answers.
(i) is injective .
(ii) is surjective .
(iii) is bijective .
Paper 4 , Section I, E
commentState the Chinese remainder theorem and Fermat's theorem. Prove that
for any prime .
Paper 4, Section I, E
comment(a) Find all integers and such that
(b) Show that if an integer is composite then .
Paper 4, Section II, E
commentWhat does it mean for a set to be countable? Prove that
(a) if is countable and is injective, then is countable;
(b) if is countable and is surjective, then is countable.
Prove that is countable, and deduce that
(i) if and are countable, then so is ;
(ii) is countable.
Let be a collection of circles in the plane such that for each point on the -axis, there is a circle in passing through the point which has the -axis tangent to the circle at . Show that contains a pair of circles that intersect.
Paper 4, Section II, E
commentState the inclusion-exclusion principle.
Let . A permutation of the set is said to contain a transposition if there exist with such that and . Derive a formula for the number, , of permutations which do not contain a transposition, and show that
Paper 4, Section II, E
commentLet be a prime. A base expansion of an integer is an expression
for some natural number , with for .
(i) Show that the sequence of coefficients appearing in a base expansion of is unique, up to extending the sequence by zeroes.
(ii) Show that
and hence, by considering the polynomial or otherwise, deduce that
(iii) If is a base expansion of , then, by considering the polynomial or otherwise, show that
Paper 4, Section II, E
comment(i) Let be an equivalence relation on a set . What is an equivalence class of ? What is a partition of Prove that the equivalence classes of form a partition of .
(ii) Let be the relation on the natural numbers defined by
Show that is an equivalence relation, and show that it has infinitely many equivalence classes, all but one of which are infinite.
Paper 4, Section I,
commentDefine the binomial coefficients , for integers satisfying . Prove directly from your definition that if then
and that for every and ,
Paper 4, Section I, E
commentUse Euclid's algorithm to determine , the greatest common divisor of 203 and 147 , and to express it in the form for integers . Hence find all solutions in integers of the equation .
How many integers are there with and
Paper 4, Section II, E
comment(i) State and prove the Inclusion-Exclusion Principle.
(ii) Let be an integer. Denote by the integers modulo . Let be the set of all functions such that for every . Show that
Paper 4, Section II, E
comment(i) What does it mean to say that a set is countable? Show directly that the set of sequences , with for all , is uncountable.
(ii) Let be any subset of . Show that there exists a bijection such that (the set of even natural numbers) if and only if both and its complement are infinite.
(iii) Let be the binary expansion of . Let be the set of all sequences with such that for infinitely many . Let be the set of all such that for infinitely many . Show that is uncountable.
Paper 4, Section II, E
comment(i) State and prove the Fermat-Euler Theorem.
(ii) Let be an odd prime number, and an integer coprime to . Show that , and that if the congruence has a solution then .
(iii) By arranging the residue classes coprime to into pairs with , or otherwise, show that if the congruence has no solution then
(iv) Show that .
Paper 4, Section II, E
commentWhat does it mean to say that the sequence of real numbers converges to the limit What does it mean to say that the series converges to ?
Let and be convergent series of positive real numbers. Suppose that is a sequence of positive real numbers such that for every , either or . Show that is convergent.
Show that is convergent, and that is divergent if .
Let be a sequence of positive real numbers such that is convergent. Show that is convergent. Determine (with proof or counterexample) whether or not the converse statement holds.
Paper 4, Section I, E
commentLet be a sequence of real numbers. What does it mean to say that the sequence is convergent? What does it mean to say the series is convergent? Show that if is convergent, then the sequence converges to zero. Show that the converse is not necessarily true.
Paper 4, Section I, E
commentLet and be positive integers. State what is meant by the greatest common divisor of and , and show that there exist integers and such that . Deduce that an integer divides both and only if divides .
Prove (without using the Fundamental Theorem of Arithmetic) that for any positive integer .
Paper 4, Section II,
comment(i) What does it mean to say that a set is countable? Show directly from your definition that any subset of a countable set is countable, and that a countable union of countable sets is countable.
(ii) Let be either or . A function is said to be periodic if there exists a positive integer such that for every . Show that the set of periodic functions from to itself is countable. Is the set of periodic functions countable? Justify your answer.
(iii) Show that is not the union of a countable collection of lines.
[You may assume that and the power set of are uncountable.]
Paper 4, Section II, E
commentLet be a prime number, and integers with .
(i) Prove Fermat's Little Theorem: for any integer .
(ii) Show that if is an integer such that , then for every integer ,
Deduce that
(iii) Show that there exists a unique integer such that
Paper 4, Section II, E
(i) Let and be integers with . Let be the set of -tuples of non-negative integers satisfying the equation . By mapping elements of to suitable subsets of of size , or otherwise, show that the number of elements of equals
(ii) State the Inclusion-Exclusion principle.
(iii) Let be positive integers. Show that the number of -tuples of integers satisfying