# Problem with modular arithmetic quiz [duplicate]

Calculate $$181^{-1} (mod\,29)$$. As part of the calculation write $$181 * A ≡ B (mod\,29)$$ where $$A \& B$$ between 0 and 28.

These are my calculations:

$$181 (mod\,29) ≡ 7(mod\,29)$$

$$=>181^{-1}(mod\,29) ≡ 7^{-1} (mod\,29)$$

Because 29 is a prime number, so with fermat's theorem: $$7^{28} (mod\,29) ≡ 1$$

$$7^{-1} (mod\,29) ≡ 7^{27} (mod\,29) ≡ 7 * 7^{26} (mod\,29) ≡ 181 * 7^{26} (mod\,29)$$

$$A = 7^{26} (mod\,29) = 16$$

$$B = 7^{27} (mod\,29) = 25$$

It was incorrect so I'm hoping someone points out my mistake.

• Umm.... you never actually calculated what $181^{-1}$ was. ANd you didn't use it to make you equation. But if you had and $181^{-1} = 25$ then you could chose arbitrary $B$ and solve for $A = 181^{-1}B = 25 B$ Aug 27, 2020 at 7:59
• $181^{-1}\equiv 7^{27}\equiv 25$ is correct, but there are simpler ways to compute it (see the linked dupes). This means $\,181\cdot 25\equiv 1\,$ so we can choose $\,A\equiv 25,\ B\equiv 1\$ (rather than scale them by $7^{-1}$ as you essentially did). Aug 27, 2020 at 14:16

We have $$181\equiv7\mod{29}$$, as you said. We know $$4\cdot7=28\equiv-1\mod{29}$$, so $$7(-4)\equiv1\mod{29}$$ or $$181\cdot25\equiv1\mod{29}$$ and $$181^{-1}\equiv25\mod{29}$$

I don't really understand your calculation, so I can't really point out your mistake. In particular, I don't see where you ever write some thing in the form $$181A\equiv B\mod{29}$$ with $$A$$ and $$B$$ between $$0$$ and $$28$$. You are correct that the answer is $$7^{27}$$ but I don't know how you reduced that to $$25$$ modulo $$29$$.

$$181^{-1} \equiv 7^{-1}$$ but what is that. You could do $$7^{-1}\equiv 7^{27}$$ and do successive squaring but that's a pain.

We need $$7x \equiv 1 \pmod 29$$. Let's pretend I don't see $$7*4 \equiv -1$$ so $$7*(-4)\equiv 1$$ and instead do that there is an integer $$k$$ so that $$7x = 29k + 1$$ so $$x = 4k+ \frac{k+1}7\in \mathbb Z$$ so $$k\equiv -1 \pmod 7$$ say if $$k = -1$$ then $$x \equiv -4\equiv 25 \pmod {29}$$

Now we use that to come up with examples where $$181*A = B$$ means $$A\equiv 181^{-1}*181 A\equiv 181^{-1}*B \equiv 25B$$ so if, say $$B=2$$ then $$A\equiv 50\equiv 21$$, for example.

Actually, as a problem being asked of you, this was a pretty stupid one. You could have found an equation just as easily by arbitrarily choosing an $$A$$, say $$A=2$$ and letting $$B\equiv 181A \equiv 7A \equiv 7*2\equiv 14$$ so $$B = 14$$.

I wouldn't have marked yours incorrect. But you never actually stated $$181^{-1}\equiv 25$$ and you didn't use that to calculate $$A,B$$.