Think of a Number/Examples/Bachet/2

From ProofWiki
Jump to navigation Jump to search

Classic Problem

The subject chooses a number less than $60$
and tells you the remainders when it is divided by $3$, $4$ and $5$, separately, not successively.
The original number is -- what?


Solution

Let $x$ be the number chosen.

Let $A$, $B$ and $C$ be the remainders on dividing $x$ by $3$, $4$ and $5$ respectively.

Then the original number is the remainder when dividing $40 A + 45 B + 36 C$ by $60$.


Proof

We have that:

\(\ds x\) \(=\) \(\ds 3 a + A\)
\(\ds \) \(=\) \(\ds 4 b + B\)
\(\ds \) \(=\) \(\ds 5 c + C\)
\(\ds \leadsto \ \ \) \(\ds 40 x\) \(=\) \(\ds 120 a + 40 A\)
\(\ds 45 x\) \(=\) \(\ds 180 b + 45 B\)
\(\ds 36 x\) \(=\) \(\ds 180 c + 36 C\)
\(\ds \leadsto \ \ \) \(\ds 121 x\) \(=\) \(\ds 60 k + \paren {40 A + 45 B + 36 C}\) for some integer $k$

So $40 A + 45 B + 36 C$ has the same remainder on dividing by $60$ as does $x$.

Because $x$ has been chosen to be less than $60$, the result follows.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Think_of_a_Number/Examples/Bachet/2&oldid=481397"