Sixth Term Examination Paper (STEP) Problem-Solving, Proof and Mathematical Reasoning Flashcards

24 sample cards from the Problem-Solving, Proof and Mathematical Reasoning deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. Describe the Euclidean algorithm for computing $\gcd(a,b)$.

   Repeatedly apply the division algorithm: replace $(a,b)$ with $(b, a \bmod b)$ until the remainder is $0$; the last non-zero remainder is $\gcd(a,b)$. It relies on $\gcd(a,b)=\gcd(b, a-qb)$.

2. State Bézout's identity.

   For integers $a,b$ (not both zero), there exist integers $x,y$ such that $ax+by=\gcd(a,b)$. Consequently $\gcd(a,b)$ is the smallest positive integer expressible as an integer combination of $a$ and $b$.

3. Define congruence modulo $n$: what does $a \equiv b \pmod{n}$ mean?

   $a \equiv b \pmod{n}$ means $n \mid (a-b)$, i.e. $a$ and $b$ leave the same remainder on division by $n$. Equivalently $a=b+kn$ for some integer $k$.

4. Which arithmetic operations are compatible with congruences modulo $n$?

   If $a\equiv b$ and $c\equiv d \pmod{n}$, then $a+c\equiv b+d$, $a-c\equiv b-d$, and $ac\equiv bd \pmod{n}$. Powers follow: $a^{k}\equiv b^{k}$. Division/cancellation is only valid when the factor is coprime to $n$.

5. State Fermat's Little Theorem.

   If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1 \pmod{p}$. Equivalently, for any integer $a$, $a^{p}\equiv a \pmod{p}$.

6. Define a prime number and explain why $1$ is not counted as prime.

   A prime is an integer $p>1$ whose only positive divisors are $1$ and $p$. The number $1$ is excluded so that the fundamental theorem of arithmetic (unique factorisation) holds; otherwise factorisations would not be unique.

7. State the fundamental theorem of arithmetic.

   Every integer $n>1$ can be written as a product of primes, $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$, and this factorisation is unique up to the order of the factors.

8. Outline Euclid's proof that there are infinitely many primes.

   Suppose there are finitely many primes $p_{1},\dots,p_{k}$. Consider $N=p_{1}p_{2}\cdots p_{k}+1$. $N$ leaves remainder $1$ on division by each $p_{i}$, so no listed prime divides $N$; yet $N$ has a prime factor. This contradicts the list being complete, so there are infinitely many primes.

9. State the binomial theorem and the formula for a binomial coefficient.

   $(x+y)^{n}=\sum_{r=0}^{n}\binom{n}{r}x^{n-r}y^{r}$, where $\binom{n}{r}=\frac{n!}{r!(n-r)!}$ is the number of ways to choose $r$ objects from $n$.

10. State Pascal's rule and the symmetry identity for binomial coefficients.

    Pascal's rule: $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$. Symmetry: $\binom{n}{r}=\binom{n}{n-r}$. Also $\sum_{r=0}^{n}\binom{n}{r}=2^{n}$.

11. State the pigeonhole principle in its basic and generalised forms.

    Basic: if $n+1$ objects are placed into $n$ boxes, at least one box contains $\geq 2$ objects. Generalised: if $N$ objects go into $k$ boxes, some box contains at least $\left\lceil \frac{N}{k}\right\rceil$ objects.

12. Give a classic pigeonhole application about subsets summing equally / common differences.

    Among any $n+1$ integers chosen from $\{1,2,\dots,2n\}$, two must be coprime (consecutive), and two must satisfy one dividing the other. More generally, choosing more numbers than available residue classes forces two with equal remainders modulo $n$, so their difference is divisible by $n$.

13. What is a functional equation, and what is the most common first strategy for solving one?

    A functional equation is an equation where the unknown is a function $f$, holding for all values in its domain, e.g. $f(x+y)=f(x)+f(y)$. The standard first strategy is substitution of special values (e.g. $x=0$, $y=0$, $y=x$, $x \to -x$) to extract properties like $f(0)$, symmetry, or injectivity.

14. What general solution does the Cauchy functional equation $f(x+y)=f(x)+f(y)$ have under mild regularity (e.g. continuity or monotonicity)?

    Under continuity (or monotonicity, or boundedness on an interval), the only solutions are linear: $f(x)=cx$ for a constant $c=f(1)$. Without such regularity, pathological non-linear solutions exist (not constructible explicitly).

15. In a long multi-part STEP question, why are earlier parts important and how should you use them?

    Earlier parts are usually scaffolding: they establish lemmas, special cases, or identities meant to be reused in later parts. You should look to apply a previously proved result, substitute a particular value, or mimic an earlier method ('Hence...') rather than starting afresh — 'Hence' signals you must use the prior result.

16. What is the distinction between 'Hence' and 'Hence or otherwise' in STEP instructions?

    'Hence' requires you to use the immediately preceding result/method to obtain the answer. 'Hence or otherwise' allows you to use the previous result (usually the intended, shorter route) or any other valid method, but the previous part is normally the efficient path.

17. What does it mean to generalise versus specialise a problem, and why are both useful?

    Specialising means testing particular/simple cases (small $n$, symmetric values, boundary values) to gain insight or spot patterns. Generalising means proving a stronger or broader statement that may actually be easier to prove by induction or symmetry. Both reveal structure; specialise to conjecture, generalise to prove.

18. How can exploiting symmetry simplify a problem?

    If an expression or constraint is unchanged under swapping or permuting variables (symmetric), the optimum or solution often occurs at the symmetric point (all variables equal), and you may assume an ordering (e.g. WLOG $a\leq b\leq c$) to reduce cases without loss of generality.

19. What is meant by translating between algebraic, geometric and graphical viewpoints? Give an example.

    It means re-expressing a problem in whichever representation makes it tractable. Example: the inequality $|x-a|<r$ (algebra) is the interval/distance condition that $x$ lies within $r$ of $a$ (geometry), which is the region between two vertical lines or under a graph (graphical). Roots of $f(x)=g(x)$ are intersection points of curves $y=f(x)$ and $y=g(x)$.

20. What makes a written solution 'rigorous and fully justified' in STEP?

    Every step must follow logically with stated reasons; assumptions are declared, quantifiers ('for all', 'there exists') are explicit, cases are exhaustive, edge cases handled, and conclusions clearly stated. No unjustified leaps, no claims of 'obviously' without warrant, and the final answer addresses exactly what was asked.

21. List three checks you can run on a result to test its plausibility (sanity checks).

    (1) Limiting/extreme cases: does the formula behave correctly as a variable $\to 0$, $\to \infty$, or at a symmetric value? (2) Dimensions/units consistency: both sides must have matching dimensions. (3) Special values / symmetry: substitute known easy values, check symmetry the answer should possess, and verify sign/magnitude are reasonable.

22. How does a dimensional (units) check catch errors in a physics-flavoured result?

    Each additive term and both sides of an equation must have identical dimensions. If a derived formula gives, say, a length added to an area, or a velocity equal to an acceleration, the algebra contains an error. Dimensional consistency is necessary (though not sufficient) for correctness.

23. What is the value of checking limiting cases such as $n=1$ or $x\to 0$ in a derived formula?

    Substituting a simple or boundary value into a general result tests it against an independently known answer: if the formula fails the easy case, it is wrong. Limiting behaviour (e.g. an expression tending to $0$, $1$, or $\infty$ as expected) confirms the general form is plausible.

24. What is the standard method to prove a divisibility statement like '$6 \mid n^{3}-n$ for all integers $n$'?

    Factor: $n^{3}-n=(n-1)n(n+1)$, the product of three consecutive integers. Among any three consecutive integers one is divisible by $3$ and at least one by $2$, so the product is divisible by $2\times 3=6$. (Alternatively prove by induction or by checking residues mod $6$.)

What this deck covers

Problem-Solving, Proof and Mathematical Reasoning flashcards FAQ