Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Question

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$.

It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I designed them this way. But surprisingly however I design the numbers the largest $x$ which leaves the same reminder is $kq_1-kq_2=k(q_1-q_2)$. Why is that? In this case we have $52 = 6\times 8+ \color \red 4$ and $46 = 6\times 7 + \color \red 4$.

Now suppose there are three numbers $a$, $b$, $c$ and $x$(assuming $a>b>c \geq x$) such that $x$ leaves the same reminder when we divide each of $a,b$ and $c$ with it. $x$ is supposed to be the largest possible value that holds the assertion. Now $x$ is given by the H.C.F of $a-b, a-c$ and $b-c$. Why is that? How can we prove this mathematically?

Answer 1

Here's my attempt at a step-by-step answer that does not use the notion of modular arithmetic.

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$.

It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I designed them this way. But surprisingly however I design the numbers the largest $x$ which leaves the same reminder is $kq_1-kq_2=k(q_1-q_2)$. Why is that? In this case we have $52 = 6\times 8+ \color \red 4$ and $46 = 6\times 7 + \color \red 4$.

Let $a$ and $x$ be positive integers. The integer quotient of $a$ and $x$ is the largest integer $q$ such that $qx\le a$. The remainder of $a$ on division by $x$ is $r=a-qx$; it necessarily satisfies $0\le r<x$.

Observe first that $kq_1-kq_2=(a-r)-(b-r)=a-b$, where $r$ is the common remainder of $a$ and $b$ on division by $k$. So your statement could be rephrased as "the largest $x$ that leaves the same remainder is $a-b$." We prove this.

Let $a>b$, and $x$ be positive integers. Let $q_a$ and $q_b$ be the corresponding integer quotients and let $r_a$ and $r_b$ be the corresponding remainders on division by $x$.

For $a$ and $b$ to have the same remainder on division by $x$ means $r_a=r_b$ which means that $a-q_ax=b-q_bx$. This implies that $a-b=x(q_a-q_b)$. So if $a$ and $b$ have the same remainder on division by $x$, then $a-b$ is an integer multiple of $x$.

Conversely, if $a-b$ is an integer multiple of $x$, then $a-b=qx$ and therefore $a=b+qx$ for some integer $q$. Since $r_a=a-q_ax$ and $r_b=b-q_bx$, we have $$ r_a=b+qx-q_ax=r_b+q_bx+qx-q_ax=r_b+(q_b+q-q_a)x. $$ We claim that $q_b+q-q_a=0$, and therefore $r_a=r_b$. This follows since $0\le r_a,r_b<x$, so $-x<r_a-r_b<x$. The only integer multiple of $x$ in this range is $0\cdot x$. We have shown that if $a-b$ is a multiple of $x$, then $r_a=r_b$.

So $a$ and $b$ have the same remainder on division by $x$ if and only if $a-b$ is divisible by $x$. The largest $x$ such that $a$ and $b$ have the same remainder on division by $x$ must therefore be the largest integer that divides $a-b$. This is $a-b$ itself.

Now suppose there are three numbers $a$, $b$, $c$ and $x$(assuming $a>b>c>x$) such that $x$ leaves the same reminder when we divide each of $a,b$ and $c$ with it. Now $x$ is given by the H.C.F of $a-b, a-c$ and $b-c$. Why is that? How can we prove this mathematically?

We build on the previous proof to prove this one. Any two of $a$, $b$, $c$ have the same remainder on division by $x$ if and only if their difference is divisible by $x$. So $a$, $b$, and $c$ all have the same remainder on division by $x$ if and only if all of the differences, $a-b$, $a-c$, and $b-c$ are divisible by $x$. The largest $x$ such that $a$, $b$, and $c$ all have the same remainder on division by $x$ is therefore the largest $x$ such that $x$ divides all three of $a-b$, $a-c$, and $b-c$. By definition of greatest common factor, this is the greatest common factor of $a-b$, $a-c$, and $b-c$.

Answer 2

It sounds like you've found that the largest integer $x$ such that $a\equiv b\bmod x$ is $x=a-b$ (having assumed, WLOG, that $a\geq b$). That's because, by definition, $$a\equiv b\bmod x\iff x\mid a-b$$ and the largest divisor of any integer is itself.

Answer 3

Consider the alternative. Suppose $a > b$ and $a \equiv b \mod x$ with $x > (a-b)$. That suggests that $(a - b) \equiv 0 \mod x$, which is to say that $x \mid (a - b)$. But if $x > (a - b)$, that's impossible.

Answer 4

Your claim is not correct. Let $a=13$, $b=7$, $c=1$, $x=2$.

Clearly, $a=b=c = 1 \mod x$. So your assumptions are met.

Then $$ a-b = 13-7 = 6$$ $$ b-c = 7-1 = 6 $$ $$ a-c = 13-1 = 12.$$

Obviously, $\mathrm{gcd}(6,6,12) = 6 \neq 2 = x$.

This leads to a contradiction, and hence your statement is not correct.

Answer 5

Assume $a=k\alpha + r_1$ and $b=k\beta + r_1$,with $a\gt b$, so we have $x=a-b=k(\alpha-\beta)$, which is the distance between the two numbers. It is obvious the there cannot be a $y\gt x$ with your property, as either $y$ would surround both $a$ and $b$ or one end of the $y$ interval would be between $a$ and $b$, but equality of remainder would only occur if $y=x$.

So a distance $y$ not $x$ must be $\lt x$, and as $y=1$ gives a remainder $0$ which must be less than or equal to the original remainder, we have $1\lt y\lt x$.

Next we can prove that $gcd(x,y)\gt1$, as if not and $tgcd(x,y)=1$ , the remainder of $b$, $b\mod y$ is clearly different to $a \mod y$. If they were the same we would have $a-b\equiv 0\mod y$ and so $y|(a-b) \to y|x$, a contradiction.

But it is impossible for such a $y$ to give a remainder larger than $x$, as if $ky=x$ say, and we had $b\equiv c \mod x$, then $b\equiv (c-jy) \mod (x+jy)$ for as long as $c-jy$ is positive (i.e. $x+jy\le b$), and so is a smaller residue.

The case for three and more numbers in an arithmetic progression can be seen from seeing that in each cased the maximal $x$ be a factor of each of $a-b$, $a-c$ and $b-c$, and so must the highest common factor. This needs the additional proof that if $gcd(m,n)\gt1$ and $m\lt n$ then $remainder(m)\le remainder(n)$, which is essentially the same proof as in the previous paragraph.

Answer 6

Unfortunately, your claim is incorrect. The best you can say is that if three numbers $a$, $b$, and $c$ have the same remainder by division by $x$, then their differences are multiples of $x$, not equal to $x$.

There are many examples that show this, for example, when $a=15$, $b=9$, $c=3$ and $x=2$, then $a$ has remainder $1$ when divided by $2$, $b$ has remainder $1$ when divided by $2$, and $c$ has a remainder of $1$ when divided by $2$. Their differences, however are $15-9=6$, $9-3=6$, and $15-3=12$, all of which are divisible by $6$, which is only a multiple of $2$, not equal to $2$.

One can prove the following claim: Suppose that $a$ and $b$ have the same remainder when divided by $x$. Then $x$ divides $a-b$.

Proof: Suppose that the remainder of $a$ divided by $x$ is $r$. Then $a=q_1x+r$. By assumption $b$ has the same remainder, so $b=q_2x+r$. Then $a-b=(q_1-q_2)x$, which is an integer times $x$, so the difference is a multiple of $x$, but not necessarily equal to $x$ (when $q_1-q_2\not=1$).

A corollary of this is that the HCF of $a-b$, $a-c$, and $b-c$ will be divisible by $x$, but still may be not equal to $x$, unless you choose the values in a lucky way. The problem with the example above is that for $a$, $b$, and $c$, $q_a-q_b$, $q_a-q_c$, and $q_b-q_c$ are all divisible by $3$.

Answer 7

Answer for the first question:

we have $a = k q_{1} + r$ and $ b = k q_{2} + r$. (Where $a >b$, $r < k$)

We deduce that $a - k q_{1} = b- k q_{2}$.

and then,

$$k = \frac{a - b}{q_{1} - q_{2}}$$

The highest value of $k$ is when $q_{1} - q_{2} = 1$.

Let prove that it is always possible.

• Suppose that $k = a - b$

we have $a = (a - b) q_{1} + r_{1}$ and $b = (a - b) q_{2} + r_{2}$

suppose that: $r_{1} = r_{2}$

Then: $(a - b) = (a - b) (q_{1} - q_{2})$

We get: $q_{1} - q_{2} = 1$

Now let suppose that $q_{1} - q_{2} = 1$

similarly we get $r_{1} = r_{2}$

So we have just proved that:

\begin{align} (k = a - b) \Rightarrow ( (r_{1} = r_{2}) \Leftrightarrow (q_{1} - q_{2} = 1)) \end{align}

Now, let suppose that $k = a - b$, $r_{1} \neq r_{2}$ and $q_{1} - q_{2} \neq 1$

We get

\begin{align} a - b = \frac{r_{1} - r_{2}}{1 - q_{1} + q_{2}} \end{align}

It is clear from this last formulae that:

\begin{align} r_{1} \geq (a-b) \ \ \ \ \text {or } \ \ \ \ r_{2} \geq (a-b) \end{align}

which is a contradiction.

This means that:

\begin{align} (k = a - b) \Rightarrow ( (r_{1} = r_{2}) \ \ \ and \ \ \ (q_{1} - q_{2} = 1)) \end{align}

Answer 8

From the comments from the OP, it appears that the question is the following:

Let $a_1,\cdots,a_n$ be integers. Let $x=\gcd(\{a_i-a_j\}_{i,j})=\gcd(\{a_i-a_{i+1}\}_i)$ (the gcd is the same as the hcf). Then $x$ is the largest integer $y$ such that $a_i\equiv a_j\pmod y$ (i.e., have the same remainder) for all $i$ and $j$.

This is a true statement and here's the proof.

Let us first consider the equality of the gcds. Suppose $i<j$, then $a_i-a_j=(a_i-a_{i+1})+(a_{i+1}-a_{i+2})+\cdots+(a_{j-1}-a_j)$, so any common divisor of the $(a_i-a_{i+1})$'s is also a common divisor of the $a_i-a_j$.

Suppose that $z$ is an integer such that all $a_i$'s have the same remainder $r$. Then $a_i=q_iz+r$ for all $i$. In this case, $a_i-a_j=(q_i-q_j)z$, so $z$ is a common divisor of all $a_i-a_j$.

On the other hand, since $x$ is a divisor of $a_i-a_{i+1}$, $a_i-a_{i+1}=qx$ for some integer $q$. Let $r_i$ be the remainder for $a_i$ under division by $x$, then $a_i=q_ix+r_i$. Since $a_{i+1}=a_i-qx=(q_i-q)x+r_i$, the remainder of $a_{i+1}$ under division by $x$ is the same as the remainder as the division of $q_i$ by $x$. Therefore, $x$ satisfies the desired properties.

In conclusion, since every integer which satisfies the desired properties (i.e., that the $a_i$'s all give the same remainder) must divide $x$ and since $x$ also satisfies the properties, $x$ is the largest integer that satisfies the desired properties.

Answer 9

What about the case of $a=36,b=24,c=12,x=6$?

In this case, the remainder is 0 for x dividing any value, however, the differences amongst a,b, and c are either 12 or 24 where the largest value that divides these is 12 which is c. Thus, x can't always be less than c and this holds.

Answer 10

Answer for the second question.

We have \begin{align} a = k q_{1} + r_{1} \\ a = k q_{2} + r_{2} \\ a = k q_{3} + r_{3} \\ \end{align}

Where $a > b > c \geq k$.

Let suppose that $r_{1} = r_{2} = r_{3}$

We get $a - b = k (q_{1} - q_{2})$; $a - c = k (q_{1} - q_{3})$; and $b - c = k (q_{2} - q_{3})$.

We deduce that $k$ is a devider for $(a-b)$, $(a-c)$, and $(b-c)$. And the highest value for $k$ is the H.C.F of these three values.

Let prove now if $k$ is the H.C.F of $(a-b)$, $(a-c)$, and $(b-c)$, we would get $r_{1} = r_{2} = r_{3}$.

We have:

\begin{align} a - b = k (q_{1} - q_{2}) + (r_{1} - r_{2}) \\ a - c = k (q_{1} - q_{3}) + (r_{2} - r_{3}) \\ b - c = k (q_{2} - q_{3}) + (r_{2} - r_{3}) \\ \end{align}

$k$ is a devider of $(a-b)$, $(a-c)$, and $(b-c)$, so $r_{1} - r_{2} = r_{2} - r_{3} = r_{1} - r_{3} = 0$ and consequently $r_{1} = r_{2} = r_{3}$