Dear Uncle Colin,

I need to find $35^{-1} \pmod {234}$, but I’m not getting the right answer. Can you help me? ((This student attached their working.))

- It’s Not Very Easy Resolving Such Expressions

Hi, INVERSE, and thanks for your message!

We’re looking for a number $x$ such that $35x = 234n + 1$, for some value of $n$.

My first instinct is to ask “am I sure this has an inverse?” - 35 is $5 \times 7$ and $234 = 2\times 3^2 \times 13$, so we’re ok - the two numbers are coprime.

Brute force

One way to do this is to examine multiples of 35 until we find one that fits the bill.

  • $7\times 35 = 245 \equiv 11 \pmod{234}$
  • $14 \times 35 = 490 \equiv 22 \pmod{234}$
  • $21 \times 35 = 735 \equiv 33 \pmod{234}$
  • $27 \times 35 = 945 \equiv 9 \pmod{234}$

I don’t know about you, but I’m bored already. We have machines for this sort of thing.

Fives and sevens

We can be a bit cleverer than this because we can factorise 35 as $5\times 7$. In particular, we can say $35x = (5a)(7b)$ for some value of $a$ and $b$. If both $5a$ and $7b$ are congruent to 1, modulo 234, we’re flying!

It’s easy to find $a$: $47 \times 5 = 235$, so $a= 47$ works.

$b$ is harder: 235 is not a multiple of 7 (231 is the closest one to 234). However, if we try 469, we see that it’s $67 \times 7$ - so $b=67$.

So, what’s $ab$? Well, multiplying those together gives 3,149. Technically, that’s an inverse. However, it’s not quite as we want it: ideally, our inverse will lie between 0 and 233 (inclusive) - so we need to find $3149 \pmod{234}$.

I’d first take away 2340 to get 809. Then I’d work out that $3\times 234 = 702$ and take that away to get 107. That is in the interval we want - and $107 \times 35 \equiv 1 \pmod {234}$.

So, in $Z_{234}$, $35^{-1} = 107$.

Another method

From what we worked out above:

  • $7 \times 35 \equiv 11 \pmod{234}$
  • $27 \times 35 \equiv 9 \pmod{234}$
  • So $20 \times 35 \equiv -2 \pmod{234}$…
  • … and $\left(27 + 4\times20\right)\times 35 \equiv (9 + 4\times(-2)) \pmod {234}$, which is 1.

That works out to be 107, as we had before!

Hope that helps!

- Uncle Colin