Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What your book is probably saying is that $3\cdot 5 = 14 \equiv 1 \mod 7$, $3 \cdot 10 = 30 \equiv 2 \mod 7$. –  Pedro Tamaroff Jul 11 '12 at 18:18
1  
Modular_multiplicative_inverse and Cayley_table –  user2468 Jul 11 '12 at 18:23
add comment

4 Answers

up vote 5 down vote accepted

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}$.

share|improve this answer
add comment

$\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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.