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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9375764727592468, "perplexity": 427.38996519046486}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-10/segments/1614178369553.75/warc/CC-MAIN-20210304235759-20210305025759-00008.warc.gz"}