1
$\begingroup$

I'm trying to solve $(x \mod 7) - (x \mod 8) = 5$ but no idea where to start. Help appreciated!

$\endgroup$
  • $\begingroup$ You can start by trying to narrow down the possible values of $x$ modulo $7$ and $8$. The equation $a - b = 5$ doesn't have very many solutions if we require that $a$ and $b$ are both non-negative, and that $a$ is less than $7$. $\endgroup$ – Dylan Oct 17 '18 at 18:41
  • $\begingroup$ Are you familiar with the Chinese remainder theorem? $\endgroup$ – Micah Oct 17 '18 at 18:41
  • $\begingroup$ Are you (incorrectly) assuming that $\mod n$ is the remainder function? $\endgroup$ – fleablood Oct 17 '18 at 18:51
2
$\begingroup$

If CRT = Chinese Remainder Theorem is known then we can reformulate it as

$$\begin{align} x&\equiv a\!+\!5\!\!\pmod{7},\ \ \ \overbrace{ 0\le a\!+\!5 \le 6}^{\Large \iff a\ =\ 0,1}\\ x&\equiv a\quad\pmod{8},\ \ \ 0\le a\le 7\end{align}\qquad \qquad\qquad $$

Solve the $\,a=0\,$ case $\,x\equiv (5,0)\bmod (7,8),\,$ then $\,x\!+\!1\equiv (6,1)\,$ yields the $\,a=1\,$ case.


W/o $ $ CRT: $\,\ \overbrace{ x-7j}^{\large x\bmod 7}-(\overbrace{x-8k)}^{\large x\bmod 8} = 5\iff 8k - 7j = 5\,\Rightarrow\, j \equiv \color{#c00}{5}\pmod{\!8},\ k\equiv \color{#c00}{5}\pmod{\!7}$

Working in the intial range $\, 0\le x\le 55\ $ and enforcing the remainder bounds

$\qquad\quad \begin{align} 0\le \overbrace{x-7\cdot \color{#c00}5}^{\large x\bmod 7} \le 6\iff 35\le x \le \color{#0a0}{41}\\[.5em] 0\le \underbrace{x-8\cdot \color{#c00}5}_{\large x\bmod 8} \le 7\iff \color{#0a0}{40}\le x \le 47\end{align}$

Therefore $\, x\equiv \color{#0a0}{40},\color{#0a0}{41}\pmod{56}$

$\endgroup$
  • $\begingroup$ Isn’t 36 a solution? Assuming $36\equiv -4 \pmod 8$ it works. $\endgroup$ – gimusi Oct 17 '18 at 19:16
  • $\begingroup$ @gimusi $\ 36\bmod 7 - (36\bmod 8) = 1 - 4 = -3\neq 5\ $ The most common convention for a complete residue system for $\,\bmod$ employs nonegative residues (vs. balanced / signed) residues. $\endgroup$ – Bill Dubuque Oct 17 '18 at 19:18
  • $\begingroup$ Ah ok we are assuming the non negative residues! Otherwise we can find other solutions. $\endgroup$ – gimusi Oct 17 '18 at 19:24
1
$\begingroup$

I'm going to assume you are incorrectly assuming $\mod n$ refers to the remainder function and want to solve $(x \% 7) -(x\% 8) = 5$ where $a \% b$ is the unique remainder when $a$ is divided by $b$.

$x \% 7 = a$ means $x = 7k + a$ for some integer $k$ and integer $0 \le a < 7$. So $a = x - 7k$.

And $x \% 8 = b$ means $x = 8j + b$ for some integer $j$ and integer $0 \le b < 8$. So $b = x - 8j$

So $a - b = 8j - 7k = 5$. By Bezout Lemma solutions exist. Let's find them.

$8*1 - 7*1 = 1$ so $8*5 - 7*5 =5$ is such a solution and $x = 5*7 + a = 35+a$ and $x = 5*8 + b = 40+b$ which can work with $a = 5$ or $6$ and $b = 0$ or $1$.

So $x = 40$ or $41$ will be solutions.

$\endgroup$
1
$\begingroup$

Suppose $x\neq 0$ then assuming

$$x=z+7k$$

with $z\neq 0$ we obtain

$$z-z-7k\equiv 5 \pmod 8$$

$$k\equiv 5 \pmod 8$$

and if

$$x=7k$$

we obtain

$$-k-7k\equiv 5 \pmod 8$$

$$0\equiv 5 \pmod 8$$

Therefore without any limit in the residues we have infinitely many solutions in the form

$$x=z+35 \quad z\not\equiv 0 \pmod 7$$

for example for $x=36$

$$(36 \mod 7) - (36 \mod 8) =1-(-4)= 5$$

for $x=43$

$$(43 \mod 7) - (43 \mod 8) =8-3= 5$$

Otherwise if we assume the standard convention for a complete residue system the possible solutions are

$$x=36,37,38,39,40,41$$

and by inspection we find that only $x=40,41$ work.

$\endgroup$

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.