# Solve the equation $3x+7=6$ in $\mathbb{Z}_{13}$

The title is exercise 2.2 in The Fundamental Theorem of Algebra.

The hint for the problem is: Find the value of $\frac{1}{3}$ in $\mathbb{Z}_{13}$

(please realize that my knowledge of the subject is what I read in Chapter 2)

I have gotten that $x = -\frac{1}{3}$.

I know that $\mathbb{Z}_{13}$ is the integers modulo 13. Thus $x \equiv n \pmod{13}$? for some integer n, $0\le n < 13$.

Thus for $x – n = km$ for some integer $k$, with $m \neq 0$ and an integer.

How does m divide $(x-n)$, when $(x-n)$ is not an integer, if $x = -\frac{1}{3}$????

-
$3\times4=-1\pmod{13}$. –  Did Jun 17 '12 at 15:45
@did I get that, but not seeing the connection to x=-1/3? Could you explain? –  yiyi Jun 17 '12 at 15:47
If $x\equiv-1/3\pmod{13}$, then $3x\equiv-1\pmod{13}$. You know that $3\cdot4\equiv-1\pmod{13}$, so ... –  Brian M. Scott Jun 17 '12 at 15:48
For a beginner, one may also have to add to Brain's hint that $13$ is a prime, so inverses $\mod 13$ are unique. –  Ragib Zaman Jun 17 '12 at 15:50
@RagibZaman I know that 13 is prime, it is also the smallest prime number which when you reverse the digits, ie 31, is also a prime number. –  yiyi Jun 17 '12 at 16:00

The notation can indeed be confusing the first few times one encounters in. When one says $x=-1/3$ in the context of $\mathbb{Z}_{13}$, it is simply short-hand for saying that $x$ is some number from $0$ to $12$ such that $-3x \equiv 1 \pmod{13}.$ So remember that $x$ is not the usual real number $-1/3$, but we use this notation because it behaves like $-1/3$ would, in that $-3x=1$ in $\mathbb{Z}_{13}.$

-
thanks. I was getting very lost because of the (1/3), a fraction. I have looked on wikipedia and rutgers, but neither used method you explained. thanks alot. –  yiyi Jun 17 '12 at 15:50
@MaoYiyi You are welcome. For some practice, you should find out what $1/4$ is in $\mathbb{Z}_7$ and what is $-1/2$ in $\mathbb{Z}_5$? Also see what is $1/2$ in $\mathbb{Z}_{16}.$ Is there more than one answer there? –  Ragib Zaman Jun 17 '12 at 15:53
It is incorrect to say that "$1/3$ is not a fraction in $\mathbb Z/13$". In fact all rationals with denominator coprime to $13$ do exist mod $13$, and, just as for integers, it is quite convenient to be able to work with such fractions. Their arithmetic is the same as in $\rm\mathbb Q$. The reason that this works will be understood better when one studies fraction rings from a universal viewpoint (so-called localizations). $\qquad$ $\quad$ $\$ –  Bill Dubuque Jun 17 '12 at 16:04
@BillDubuque thanks, for that insight. I'll have to find a book on localizations. Do you know one that is not too far advance. –  yiyi Jun 17 '12 at 16:08
@MaoYiyi Although localization could be introduced in an (advanced) elementary number theory course, ususally it is not studied till after a course in abstract algebra. The point is that fraction arithmetic is universal, e.g. the equation $\rm\:1/2 - 1/3 = 1/6\:$ will remain true in any ring where $2$ and $3$ have inverses, e.g. in $\rm\:\mathbb Z/m\:$ for all $\rm\:m\:$ coprime to $6$, e.g. it becomes $\rm\:7\! -\! 9 \equiv 11\ (mod\ 13).\:$ $\quad$ $\quad$ $\$ $\$ $\$ $\$ $\,$ –  Bill Dubuque Jun 17 '12 at 16:13

Hint $\rm\ mod\,\ 3n\!+\!1\!:\ -1\equiv 3n\:\Rightarrow\:\dfrac{-1}3\,\equiv\, \dfrac{3n}3 \,\equiv\, n$

-

What you could have done also $$3x + 7 = 6\pmod{13} \implies 3x = -1 \pmod{13} \implies 3x = 12 \pmod{13}$$ At this point it should be pretty easy!

-

Note that $3x\equiv -1$ iff $3x\equiv 12$ modulo $13$. From there, it should be simple.

$x=-1/3$ only in the sense that it is the member of $\Bbb Z_{13}$ such that $3x\equiv -1$ modulo $13$. This is not the same as saying $x=-1/3$ in the sense of real numbers.

-
how is that 1/3? in mod 13? Modular arithmetic doesn't have fractions. –  yiyi Jun 17 '12 at 15:48
True, there are no fractions, here. However, there are multiplicative inverses. Perhaps it would be better if the book had said "find the value of $3^{-1}$ in $\Bbb Z_{13}$", instead? Moreover, since $13$ is a prime number, then $\Bbb Z_{13}$ is a field, and so every non-$0$ element of $\Bbb Z_{13}$ has a unique multiplicative inverse. We can't do this in $\Bbb Z_n$ for general $n$. –  Cameron Buie Jun 17 '12 at 15:52
@Cameron Actually one can do fractional arithmetic in $\rm\:\mathbb Z/13,\:$ as long as one works in the subring of rationals with denominator coprime to $13$. See my comments to Ragib's answer. –  Bill Dubuque Jun 17 '12 at 16:35
@Bill: Interesting! I haven't yet dealt with localizations, but that makes sense. –  Cameron Buie Jun 17 '12 at 16:40

We look for an integer $x$ so that 3x=-1 mod 13. This is the same as $3x+1=0 \mod 13$ or $13 | 3x+1$. Now in this case we can just run through the integers $0\le x\le 12$ to find the answer $x=4 \mod 13$.

-
You might point out that just "running through" the integers $2\leq p-1$ isn't a great plan for general primes $p$, as $p$ could be rather large.... –  Cameron Buie Jun 17 '12 at 15:57

Hint: what is $-1 \pmod {13}$ in the normal set of representatives $0 \le n \lt 13$?

-