I have the following problem:
An integer leaves a remainder of 15 when divided by 77 and a remainder of 16 when divided by 78.
What remainder leaves that integer when divided by 14?
I know that we can solve this problem by using the Chinese Remainder Theorem. However, we didn't cover this theorem in class, so the idea is to instead use the diophantine equation.
My attempt:
$a = 77x + 15$ and $a = 78y + 16$
$77x +15 = 78y + 16 \Rightarrow 77x – 78y = 1.$
Calculating GCD(77,-78) gives:
$-78 = (-2).77 + 76$
$77 = 1.76 + 1 $
$76 = 76.1 + 0$
Then applying the Extended Euclidean Algorithm:
$1=(1 . 77) + (-1 . 76)=(-1 . -78) + (-1 . 77)$
A particular solution is:
$x_{0} = -1 , y_{0}=-1$
The complete solution is:
$x = -1 – 78n$
$y = -1 – 77n$
For $n=0$ we get $x=-1$ and $y=-1$.
But now, I don't know how to proceed to find the remainder when dividing by 14.
Best Answer
For $x_0=-1$, $a=77(-1)+15=-62$ is indeed one of the infinitely many integers which are solutions to the question.
So just find $-62 \pmod {14}$.