-1

So I'm trying to find the inverse of $24$ in $\mathbb{Z}_{35}$. I know this means that there must be some $ab \equiv 1 \pmod{n}$ But when I try this:

$24b \equiv 1 \pmod{35}$

$1 = 35*0 + 1$

$24b = 1$

$b = 1/24$

But this isn't an integer, so I'm not sure what I'm doing wrong here.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Riley
  • 1
  • 4
  • 1
    Welcome to MSE! Please use the [basic tutorial and quick reference guide](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) and also show the work you have done so far. – Jessie Feb 03 '21 at 17:34
  • 1
    Welcome to Mathematics Stack Exchange. Do you know the [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)? – J. W. Tanner Feb 03 '21 at 17:35
  • that's all the work I've done, I dont know the Euclidean algorithm though – Riley Feb 03 '21 at 17:35
  • $\!\bmod 35\!:\ \dfrac{1}{24}\equiv \dfrac{36}{24}\equiv \dfrac{3}2\equiv \dfrac{38}2\equiv 19.\ $ See [here](https://math.stackexchange.com/a/2368266/242) & [here](https://math.stackexchange.com/a/3434593/242) in the linked dupes for many other handy ways. – Bill Dubuque Feb 03 '21 at 19:00

3 Answers3

0

Since $2\cdot 18 \equiv 36 \equiv 1 \pmod{35}$, you have an inverse for $2$. Since $3\cdot 12 \equiv 36 \equiv 1\pmod{35}$ you have an inverse for $3$. Since $24 = 2^3 3$ you can easily construct its inverse.

B. Goddard
  • 32,046
  • 2
  • 25
  • 62
  • It's $18^312\equiv(18\cdot2)^218\cdot3\equiv18\cdot3$ – J. W. Tanner Feb 03 '21 at 17:51
  • Easier done by reducing the fraction $\,\dfrac{1}{24}\equiv \dfrac{36}{24}\,$ see my comment on the question. – Bill Dubuque Feb 03 '21 at 19:04
  • @BillDubuque I wasn't going for easy. I was giving hint so he could work it out himself, even not knowing the Euclidean Algorithm. You and Tanner pretty much ruined that. – B. Goddard Feb 03 '21 at 21:07
  • Not sure what you mean be "ruined that". Your answer boils down to the fact that it is easy to invert a product of integers each having an [easy inverse](https://math.stackexchange.com/a/890368/242) (dividing modulus $\pm 1).\,$ This is a special case of the more general algorithms in the linked dupes. – Bill Dubuque Feb 03 '21 at 22:09
0

Start by computing $\text{gcd}(24, 35)$ using the Euclidean algorithm. We have that: \begin{align*} &35 = 24(1) + 11 \\ &24 = 11(2) + 2 \\ &11 = 2(5) + 1 \end{align*}

So $\text{gcd}(24, 35) = 1$. Our goal now is to work backwards:

\begin{align*} &11 = 2(5) + 1 \implies 1 = 11 - 2(5) \\ &24 = 11(2) + 2 \implies 1 = 11 - 5[24 - 11(2)] = 11(11) - 5(24) \\ &35 = 24 + 11 \implies 1 = 11(35 - 24) - 5(24) = 11(35) - 16(24) \end{align*}

So $11(35) - 16(24) = 1$. Thus, $24^{-1} \equiv -16 \pmod{35}$. Note that $-16 \equiv 19 \pmod{35}$.

ml0105
  • 14,401
  • 2
  • 24
  • 47
  • 1
    Doing extended euclidean backwards is both painful and highly error-prone. Instead we can use the [simpler *forward* form,](https://math.stackexchange.com/a/616893/242) or simpler ways I link in my comment on the question. – Bill Dubuque Feb 03 '21 at 19:08
  • This is a neat trick! I was not aware of it! Thanks for pointing it out! – ml0105 Feb 03 '21 at 20:43
0

Hint:

First, $1/24$ is an integer in $\mathbb{Z}_{35}$. It just doesn't look like it yet because you haven't performed the division operation. This is similar to how $0.\overline{9}$ or $1/.5$ might not look like integers, but they are.

The easiest way is to simply go through every element of $\mathbb{Z}_{35}$ and see if it is the inverse of $24$.

$1\cdot 24=24$, so $1/24\neq 1$.

$2\cdot 24=48\equiv 13$, so $1/24\neq 2$.

$\vdots$

Again, we are looking for a value that when we multiply by 24, we get 1.

ndhanson3
  • 1,335
  • 4
  • 14
  • *Brute force search* is rarely the "easiest way" to compute modular inverses and fractions. See my comment on the question for many truly easy ways that work generally. – Bill Dubuque Feb 03 '21 at 19:03
  • My apologies. I meant most straightforward, lowest-level, easiest to understand. Given the wording and amount of understanding demonstrated in the question, I wanted to make sure what the goal of your analysis really is. – ndhanson3 Feb 03 '21 at 21:39
  • Ok, thanks for clarifying. – Bill Dubuque Feb 03 '21 at 21:57