4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

If $x\equiv16\bmod78$ and $x\equiv15\bmod77$, then $x\equiv0\bmod2$ and $x\equiv1\bmod 7$.

Can you take it from here?

But if you insist on doing it your way,

$a=77x+15=78y+16$ with $x=y=-1$

so $a\equiv 77(78n-1)+15\equiv 78(77m-1)+16\bmod (77\times78)\equiv5944\bmod6006$.

Now can you find the remainder mod $14$?

$\endgroup$
2
$\begingroup$

$$N = 77x + 15=78y + 16$$

$$N+62 = 77x + 77=78y + 78$$

$$LCM(78;77)=6006$$

$$N+62=6006k, k \in Z$$

$$6006k-62\equiv -62\equiv 8 \pmod {14}$$

$\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.