6
$\begingroup$

I just want to confirm I am doing this problem correctly.

The problem asks to compute without a calculator: $$ 3 * \frac{2}{5} \pmod 7 $$ The way I am solving the problem: $$ 3 * \frac{2}{5} \bmod 7 \\ 3 * 2 * \frac{1}{5} \bmod 7\\ \gcd(5,7) = 1 (\text{inverse exists}) $$ $$ (((3 \bmod 7) * (2 \bmod 7) * (1 \bmod 7)) \bmod 7) \\ (3 * 2 * 1) \bmod 7 $$ $$ 6 \bmod 7 = 6 $$

Am I doing this correctly? Just started learning this in class. This is an even number practice problem out the book so I cannot check the answer lol.

$\endgroup$
  • $\begingroup$ Actually $\frac15=5^{-1} \pmod{7}$ would be an integer $c$ for which $5c\equiv 1\pmod{7}$. It appears that you're trying to use $1$ as the inverse of $5$ $\mod{7}$ $\endgroup$ – paw88789 Sep 6 '14 at 2:10
2
$\begingroup$

We want to find $(3)(2)(x)\pmod{7}$, where $x$ is the inverse of $5$ modulo $7$, that is, where $5x\pmod 7=1$.

There are general procedures for finding inverses modulo $m$, but $7$ is a very small number, so we can do it efficiently by trial and error. Note that $(5)(3)$ has remainder $1$ on division by $7$. So $x\pmod 7=3$.

Thus we want to compute $(3)(2)(3)\pmod 7$. This is $4$.

$\endgroup$
  • $\begingroup$ Thank you very much! Makes a lot more sense now lol $\endgroup$ – BinaryDude87 Sep 6 '14 at 2:21
  • $\begingroup$ You are welcome. One just needs to remember that "division" is multiplication by the (multiplicative) inverse, just like ordinary division by $w$ is multiplication by the reciprocal of $w$. $\endgroup$ – André Nicolas Sep 6 '14 at 2:23
4
$\begingroup$

Hint $\,\ {\rm mod}\ 7\!:\,\ \color{#c00}{5\equiv -2}\,\Rightarrow\, \dfrac{3\cdot 2}{\color{#c00}5}\equiv \dfrac{3\cdot 2}{\color{#c00}{\,-2}}\equiv -3\equiv 4 $

Beware $ $ While, as usual, fractions may serve to greatly simplify arithmetic, their modular analog increases the probability of division exceptions, since the modular analog of "you can't divide by $0$" is "you can't divide by a zero-divisor", i.e. divisors and denominators $d$ must be coprime to the modulus $m$ ($\!\iff\! d$ is invertible mod $m)$ for the quotient to be well-defined. Then the fraction $\,c/d \equiv cd^{-1}$ and the usual grade-school arithmetic is true for such fraction expressions, e.g. the addition law $\,a/b+c/d = (ad+bc)/(bd)\,$ holds because $$\,(ad+bc)\color{#0a0}{(bd)^{-1}}\equiv ad\,\color{#0a0}{d^{-1}b^{-1}}+ \color{#0a0}{d^{-1}b^{-1}}bc\equiv ab^{-1}+d^{-1}b $$

Recall that by Euclid: $\,b,d\,$ coprime to $m$ $\iff$ $bd$ coprime to $m,\,$ indeed $\,\color{#0a0}{(bd)^{-1}\! \equiv d^{-1}b^{-1}}$ so the fractions in the addition rule are all well-defined, i.e. have denominators coprime to $m.\,$ It is essential to restrict to such fractions else one can deduce contradictions such as the following: ${\rm mod}\ 10\!:\,$ $\,0\equiv 0/2\equiv 10/2\equiv 5.\,$ Let's examine more closely what goes wrong here.

Generally a fraction $\,x \equiv a/b\,$ with noninvertible denominator (not coprime to modulus) is not well-defined because the equation $\,b x \equiv a\,$ does not have a unique solution, i.e. there may be no solutions, or there may be more than one solution. For example, mod $\rm 10,$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}\,$ cannot designate a unique solution of $\,4x\equiv 2.\,$ Indeed, the solution is $\rm\:x\equiv 1/2\equiv 3\pmod 5,\,$ which requires canceling $\,2\,$ from the modulus too, because $\rm\:10\:|\:4x-2\iff5\:|\:2x-1.\,$ An unsolvable example is the fraction $\,x \equiv 1/4,\,$ since $\,10\mid 4x-1\,\Rightarrow 10n = 4x-1\,$ $\Rightarrow$ $\,4x-10 = 1\,$ is even, contradiction. See here for further discussion, including use of multi-valued modular fractions in the Extended Euclidean Algorithm.

Ring-theoretically, this may be viewed as a generalization of the fact that division by zero is not well-defined, i.e. division by a $\,\rm\color{#c00}{zero\!-\!divisor}\,$ is not well-defined (in a nontrivial ring), since if $\,\color{#c00}{bc=0,\ b,c\ne 0}\,$ then $\,bx = a\,\Rightarrow\,\color{#c00}b(\color{#c00}c\!+\!x) = a\,$ so if a solution $\,x\,$ exists then it is not unique.

Generally the grade-school rules of fraction arithmetic apply universally (i.e. in all rings) where the denominators are all invertible, e.g. $\, 1/2 - 1/3 = 1/6\,$ can be interpreted in any ring where $6$ is invertible, e.g. in the integers mod $n$ for all $n$ coprime to $6$, e.g. mod $5$ it is $3-2\equiv 1,\,$ and mod $11$ it is $6 - 4 \equiv 2$. This fundamental universal property of fractions will be clarified conceptually when one learns in university algebra about the universal properties of fractions rings (and localizations).

$\endgroup$
  • $\begingroup$ Hi Bill, I know thjis answer is pretty old, but could you explain a bit how to reach the conclussion that the rules of fraction arithmetic apply to all the units of rings? Thanks. $\endgroup$ – YoTengoUnLCD May 15 '15 at 21:51
  • $\begingroup$ @YoTengoUnLCD It is not easy to make that precise before one learns about localizations. Informally, it is true because such fraction arithmetic uses only the ring axioms augmented by the hypotheses that all occuring denominators are invertible, so the result will persist in any image of the ring satisfying these properties, e.g. $\, 1/2 - 1/3 = 1/6\,$ remains true in any ring where $\,2\,$ and $\,3\,$ are invertible, e.g. that becomes $\,4+2 = 6\pmod 7$. Or, interpreted multiplicatively, if $\,a\,$ has a square root $\,b\,$ and cube root $\,c\,$ then it has a sixth root $\,b/c.\ \ $ $\endgroup$ – Bill Dubuque May 15 '15 at 22:27
  • $\begingroup$ I was thinking $3 \cdot \frac 25 \equiv 10 \cdot \frac 25 \equiv 2 \cdot 2 \equiv 4 \pmod 7$ $\endgroup$ – steven gregory Mar 22 at 12:15
  • $\begingroup$ @steven Yes, that works too. There are typically many ways to evaluate them. $\endgroup$ – Bill Dubuque Mar 22 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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