# How to solve $(x \mod 7) - (x \mod 8) = 5$?

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

• 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$. – Dylan Oct 17 '18 at 18:41
• Are you familiar with the Chinese remainder theorem? – Micah Oct 17 '18 at 18:41
• Are you (incorrectly) assuming that $\mod n$ is the remainder function? – fleablood Oct 17 '18 at 18:51

## 3 Answers

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

• Isn’t 36 a solution? Assuming $36\equiv -4 \pmod 8$ it works. – gimusi Oct 17 '18 at 19:16
• @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. – Bill Dubuque Oct 17 '18 at 19:18
• Ah ok we are assuming the non negative residues! Otherwise we can find other solutions. – gimusi Oct 17 '18 at 19:24

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.

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.