skip to content

STEP Support Programme

Assignment 17, question 1

I'm not sure I get some parts of the modulo function. I'll run through what I did in the first part and then go through what I don't get about the second.

Okay, so for the first part I put that xmoda = (x+k)moda, where k is any multiple of a. Later, we get N1 + N2 = a(m1 + m2) + n1 + n2.
Therefore, if we put N1 + N2 into the modulo function under a, we get the same function as if we put n1 + n2. This worked for N1N2 as well.

For the second part, I just didn't know what to do. Since 10mod3 = 1, I put that 10amod3 = a. Hence, via the results we got prior, we should get bmod3 = b, which I didn't trust. So I went to the hints and found this:

10a + b = (10mod3) * (amod3) + bmod3

I'm not sure how we get this. Could someone go through how we come to this from what we're given?

With the last part, we have (amod3) + (bmod3) = (a + b), which I'm also not sure about.

You are working (mod 3) so you really need to write these at the end of the lines. So it would be wrong to write 10 (mod 3) = 10 as this is saying 1 = 10. However you can write:
\[
10 \, \text{mod } 3 \equiv 10 \quad (\text{mod } 3)
\]

Using this idea we have:
\begin{align*}
10 a + b &\equiv (10 \, \text{mod }3)\times (a \, \text{mod }3) + b \, \text{mod }3 \quad & (\text{mod }3)\\
&\equiv 1 \times a \, \text{mod }3 + b \, \text{mod }3 \quad &(\text{mod }3)\\
&\equiv (a+b) \quad &(\text{mod }3)
\end{align*}

There fore we have $(10 a + b) \equiv (a+b) \, \text{mod }3$ and so $10a+b$ is divisible by 3 if and only if $a+b$ is divisible by 3.

So where do we get (10a + b = (10mod3) * (amod3) + bmod3) from? Sorry, but I still don't understand where those things came from.

You need to be quite careful with which signs you are using. We are not saying at any point that $10=1$, but instead $10 \equiv 1 \, (\text{mod }3)$.

We have:
\begin{align*}
10 &\equiv 1 \quad (\text{mod }3)\\
5 &\equiv 2 \quad (\text{mod }3)\\
8 &\equiv 2 \quad (\text{mod }3)
\end{align*}
Note that none of these are "="!

Using "$N_1N_2 \equiv n_1n_2 \, (\text{mod }a)$" and "$N_1+N_2 \equiv n_1+n_2 \, (\text{mod }a)$" we have:
\begin{align*}
58 &= 5 \times 10 + 8 \quad \text{note this is not working in mod 3 yet, hence equals sign!}\\
58 &\equiv (5 \, \text{mod }3) \times (10 \, \text{mod }3)+ (8 \, \text{mod }3) \quad (\text{mod }3)\\
&\equiv 2 \times 1 + 2 \quad (\text{mod }3)\\
&\equiv 4 \quad (\text{mod }3)\\
&\equiv 1 \quad (\text{mod }3)
\end{align*}
Which is what we expect has $58$ has a remainder of 1 when divided by 3.

Useful Links

Underground Mathematics: Selected worked STEP questions

STEP Question database

University of Cambridge Mathematics Faculty: What do we look for?

University of Cambridge Mathematics Faculty: Information about STEP

University of Cambridge Admissions Office: Undergraduate course information for Mathematics

Stephen Siklos' "Advanced Problems in Mathematics" book (external link)

MEI: Worked solutions to STEP questions (external link)

OCR: Exam board information about STEP (external link)

AMSP (Advanced Maths Support programme): Support for University Admission Tests (external link)