Ask Uncle Colin: An Additive Inverse

Dear Uncle Colin,

I need to find ${35}^{-1}(\mathrm{mod}234)$, but I’m not getting the right answer. Can you help me? ¹

- 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(\mathrm{mod}234)$
• $14\times 35=490\equiv 22(\mathrm{mod}234)$
• $21\times 35=735\equiv 33(\mathrm{mod}234)$
• $27\times 35=945\equiv 9(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}234)$.

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

Another method

From what we worked out above:

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

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

---

Hope that helps!

- Uncle Colin

Footnotes:

1. This student attached their working.