I had to perform a division between two polinomials $2x^2+3x+4$ and $3x+4$, my book suggests to do this operation without worrying about the modulo. So my result is $(3x+4)(\frac{2}{3}x+\frac{1}{9})+\frac{32}{9}$. Unfortunately my book fails to explain how should I perform the conversion from fractions to $\mathbb Z_7$ elements, like it's kind of obvious, it only reports $\frac{1}{3}=5$, $\frac{2}{3} = 10 = 3$, $\frac{32}{9}=2$. Will you please break it down for me?
Turn fractions into $\mathbb Z_7$ elements
-
1[Modular_multiplicative_inverse](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse) and [Cayley_table](http://en.wikipedia.org/wiki/Cayley_table) – 2012-07-11
4 Answers
Remember that $\frac{1}{x}$ means "the element which, when multiplied by $x$, gives $1$."
Alternatively, $\frac{a}{b}$ is just shorthand for "the solution to the equation $bx=a$."
So, in $\mathbb{Z}_7$, the fraction $\frac{1}{3}$ is shorthand for "the solution to the equation $3x=1$", which, when interpreted in $\mathbb{Z}_7$, is just "the solution to the integer congruence $3x\equiv 1\pmod{7}$."
Similarly, $\frac{2}{3}$ means "the solution to the integral congruences $3x\equiv 2\pmod{7}$", and $\frac{32}{9}$ means "the solution to the integral congruence $9x\equiv 32\pmod{7}$."
Since $\gcd(3,7)=\gcd(9,7)=1$, each of these congruences has a unique solution modulo $7$. $3(5)\equiv 1\pmod{7}$, so $5 = \frac{1}{3}$. Hence, $\frac{2}{3} = 2\frac{1}{3}=2(5) = 10 \equiv 3\pmod{7}$, so $\frac{2}{3}$ is $3$. And since $32\equiv 4\pmod{7}$, for $\frac{32}{9}$ you have $4(5)(5) = 100\equiv 2\pmod{7}$.
$\frac 1 3=5$ because $\frac 1 3 \cdot 3=1$, and $5\cdot 3=15 \equiv 1$ in $\mathbb{Z}_7$. The others can be found similarly. You convert the fraction based on the idea that $fraction \times denominator=numerator$, and then finding the appropriate number in $\mathbb{Z}_7$ that replaces the fraction and still satisfies this relationship.
Deal first with $1/3$. In the modulo $7$ world, this is a number $x$ such that $3x\equiv 1\pmod{7}$.
How do we find such an $x$? Well $7$ is small, so try all the possibilities for $x$. These are $1$ (well, not really!), $2$, $3$, $4$, $5$, and $6$. Try $x=2$. Does it work? Let's check. We have $(3)(2)\equiv 6\pmod{7}$, doesn't work.
Try $x=3$. We have $(3)(3)=9\equiv 2\pmod{7}$, doesn't work. Try $x=4$. We have $(3)(4)=12\equiv 5\pmod{7}$, doesn't work. Try $x=5$. We have $(3)(5)=15\equiv 1\pmod{7}$. Bingo!
By the way, our first trial almost worked. We have $(3)(2)\equiv 6\equiv -1\pmod{7}$. So if we replace $2$ by $-2$, the product will be congruent to $1$. Thus $x\equiv -2\equiv 5\pmod{7}$.
Now for the $2/3$, this is easy, it is twice $1/3$. Modulo $7$, we get $10$, which is congruent to $3$.
We can get to $32/9$ in many ways. For example, to get $1/9$, square our $1/3$ found above. We get $25$, which is congruent to $4$ modulo $7$. But $32$ is congruent to $4$, so for $32/9$ we will want $(4)(4)$, which is congruent to $2$ modulo $7$.
There are much easier ways. For example, $32$ is congruent to $4$, and $9$ is congruent to $2$, so the fraction should be congruent to $\dfrac{4}{2}$, which is $1$.
Remark: The "guess and test" approach described above is only practical for relatively small primes. For larger primes, one needs a more efficient approach. You will probably learn one soon, the Extended Euclidean Algorithm.
The polynomial $\rm\, (3x+4)(\frac{2}{3}x+\frac{1}{9})+\frac{32}{9}\, $ can be evaluated in any ring where $3$ is invertible, in particular, modulo $\rm\,1\!+\!3n,\,$ since $\rm\:1\!+\!3n\equiv0\:\Rightarrow\,1\equiv -3n\:$ $\Rightarrow$ $\rm\,1/3 \equiv -n.\:$ In particular, for $\rm\:n=2,\,$ we have, $\rm\,mod\ 7\!:\ 1/3 \equiv -n\equiv -2\equiv 5,\:$ hence $\rm\:1/9 = (1/3)^2 \equiv (-2)^2\equiv 4.$