Is this proof for 1/4 mod 9 = x, correct?

Question

Find an integer x so (1/4) mod 9 = x

Proof:

> 1/4 mod 9 = x 
> 1 mod 9 = 4 * x
> - using x = 7 - 
> 1 mod 9 = 28 
> 28 mod 9 = 1 (to validate)
> - using Euler division theorem m = nq + r - 
> 28 = 9(3) + 1
> r = 1, so 1 = 1

I appreciate the feedback.

yes, with my proof, I am saying that x = 7, but I am not sure if the procedure used is valid. :) — Juan Zamora, Apr 22 '15 at 05:35

score 1 · Answer 1 · answered Apr 22 '15 at 10:09

Here is a systematic approach to finding the inverse.

Since $\gcd(4, 9) = 1$, $4$ has a multiplicative inverse modulo $9$. To find it, we must solve the equivalence $$4x \equiv 1 \pmod{9}$$ To find the solution, we can use the Euclidean Algorithm. $$9 = 2 \cdot 4 + 1$$ Solving for $1$ yields $$9 - 2 \cdot 4 = 1$$ Hence, $1 \equiv -2 \cdot 4 \pmod{9}$, so $$x \equiv -2 \equiv 7 \pmod{9}$$ Therefore, $$4^{-1} \equiv \frac{1}{4} \equiv 7 \pmod{9}$$

score 0 · Accepted Answer · answered Apr 22 '15 at 05:36

0

We have $xy\equiv1\mod n$, so logically it makes sense to write $x\equiv\frac1y \mod n$

answered Apr 22 '15 at 05:36

JMP

21,771

Thank you, that was exactly what I was not sure. – Juan Zamora Apr 22 '15 at 05:37
typically doesn't work if $x|n$ or $y|n$ @JuanZamora – JMP Apr 22 '15 at 05:41

Is this proof for 1/4 mod 9 = x, correct?

2 Answers2