Take the 2-minute tour ×

I am trying to understand a wierd symbol in a book and I am failing.

The symbol is this '$\equiv$'. I understood that if I have $32\equiv 2\bmod15$ means that if I divide $32$ with $15$ I will get $2$ as a remainder.

What if for example if i have

$$x\equiv 5 \bmod17$$ and $$x\equiv 3 \bmod23$$

How to find if there is such $x$ that satisfies both cases?

share|improve this question
"in a book" - which book? –  Ｊ. Ｍ. Dec 1 '11 at 16:36
What you need here is the Chinese remainder theorem. –  Ｊ. Ｍ. Dec 1 '11 at 16:39
It is called "Discrete Mathematics for beginners" but I think it is only available in my language. –  vellosoum Dec 1 '11 at 16:41
It is still important that you mention where you saw notation you're unfamiliar with whenever you ask questions like these. Even if the source isn't English. –  Ｊ. Ｍ. Dec 1 '11 at 16:43
add comment

4 Answers

The general meaning of '$\equiv$' is an equivalence relation. In elementary number theory the notation (due to Gauss) has the specific meaning of equivalent "modulo" an integer, namely:

$$x \equiv y \pmod{n}$$

means that $(x-y)$ is divisible by $n$.

A basic set of exercises in an elementary number theory course is to prove that this relation between integers $x,y$ is an equivalence relation for any $n \gt 0$. For $n=0$ it may be a convention to consider the notation as amounting to ordinary equality of integers.

share|improve this answer
So $(x-5)/17 = 0$ and $(x-3)/23=0$ which means $x=32/3$? –  vellosoum Dec 1 '11 at 16:52
@hardmath: I edited your post using the "\pmod" command. I hope you don't mind. –  JavaMan Dec 1 '11 at 16:57
@vellosoum: Not quite. $x\equiv 5\pmod{17}$ means that $x-5$ is divisible by $17$, so there is some integer $k$ such that $x-5=17k$. Similarly, $x\equiv 3\pmod{23}$ means that there is some integer $j$ such that $x-3=23j$. Thus, $x=17k+5=23j+3$, and $23j=17k+2$. This has infinitely many integer solutions, and each of them gives rise to a different solution to the original pair of congruences. –  Brian M. Scott Dec 1 '11 at 17:03
@BrianM.Scott Then why the book expects a value for an answer? –  vellosoum Dec 1 '11 at 17:12
@vellosoum: Your text ought to have an example of such a problem, or at least a discussion of the Chinese remainder theorem (or see here), but you can find a solution by hand. In this case a little experimentation shows that $8\cdot 17+2=6\cdot 23$, so $k=8,j=6,x=141$ is one solution. Adding or subtracting integer multiples of $17\cdot 23$ will produce others. There is only one solution satisfying $0\le x<17\cdot 23$; if it wants just one solution, that’s probably it. –  Brian M. Scott Dec 1 '11 at 17:18
add comment

As JM says, you can use the Chinese remainder theorem to solve this kind of question. You have

  • $x\equiv 5 \bmod17$ so $x = 17k +5$ for some $k$

  • $x\equiv 3 \bmod23$ so $x = 23j +3$ for some $k$

so you can look for solutions to $17 k+5=23j+3$ or equivalently $2\equiv 23j \bmod17$ which can be simplified to $2\equiv 6j \bmod17$ since $23\equiv 6 \bmod17$.

One possibility is $j=6$ since $36\equiv 2 \bmod17$, making $x=141$. To check: $141 = 8 \times 17+5 = 6\times 23+3$.

Since $17$ and $23$ are coprime, and $17\times 23 = 391$, the general solution is $141+391n$ for integer $n$.

share|improve this answer
add comment

An ancient algorithm known as the Chinese Remainder Theorem solves systems of congruences. Using a simple version that I mention here, since $\rm\:gcd(17,23) = 1\:$ we know $\rm\:1/23\:$ exists $\rm\:mod\ 17\:,\:$ and employing it easily yields the following solution

$$\rm\ x\ \equiv\ 3\ +\ (5-3)\cdot 23\cdot \bigg(\ \dfrac{1}{23}\ mod\ 17\bigg)\quad\ (mod\ 17\cdot 23) $$

Notice that, indeed, $\rm\ x\: \equiv\: 3\pmod{23}\:;\ $ also $\rm\ x\:\equiv\: 3 + (5-3)\:\equiv\: 5\pmod{17}\:,\: $ using $\ 23\cdot 23^{-1}\equiv 1\:.\ $ It remains to compute the modular inverse, which is easy with a little modular massaging

$$\rm mod\ 17\!:\ \ \frac{1}{23}\ \equiv\ \frac{18}{6}\ \equiv\ 3$$

Therefore we conclude $\rm\ x\ \equiv\ 3 + (5-3)\cdot 23\cdot 3\ \equiv 141\quad (mod\ 17\cdot 23)$

Generally one can use the extended Euclidean algorithm to compute modular inverses. However, as above, for small numbers there are often many nice coincidences (law of small numbers) that enable obvious optimizations.

share|improve this answer
add comment

There are two questions here: One is about notation and the other one about the solution of a particular problem involving this notation.

(a) The symbol $\equiv$ implying some sort of "equality" or "equivalence" is used in everyday mathematics in two completely different frameworks. In analysis an "identity" of the form

$$\sin^2 x +\cos^2 x\ \equiv\ 1$$

conveys the meaning that the equation $\sin^2 x+\cos^2x =1$ is true for all values of the variable $x$ in the actual environment of discourse, say $\bigl[0,{\pi\over2}\bigr]$, ${\mathbb R}$, or ${\mathbb C}$.

In elementary number theory the symbol $\equiv$ in an equation only has a meaning in connection with an attribute "$(\bmod m)$" stated explicitly on the right of the equation. An equation of the form $x\equiv y \pmod m$ then means that $x-y$ is divisible by the integer $m$. One might as well write an $m$ below the $\equiv$-symbol.

It follows that in your example the symbol $\equiv$ means different things in the two given equations.

(b) Concerning the particular problem I refer to other answers to your question.

share|improve this answer
add comment

Your Answer


