Series of Equivalences

Question

I got this question.

If I climb $2$ stairs at a time, $1$ is left over.
If I climb $3$ stairs at a time, $2$ are left over.
If I climb $4$ stairs at a time, $3$ are left over.
If I climb $5$ stairs at a time, $4$ are left over.
If I climb $6$ stairs at a time, $5$ are left over.
If I climb $7$ stairs at a time, $6$ are left over.
How many stairs are there?

I attempted solving like this:

$x\equiv1\pmod2$

$x\equiv2\pmod3$

$\vdots$

$x\equiv6\pmod7$

So now I have a system of six equivalences. I concluded that the unit digit of $x$ would be $9$, but could go no further.

I have heard of the Chinese Remainder Theorem, which helps in solving such problems, but the Wikipedia example is convoluted and I do not get the right answer.

Our teacher solved like this:

Each number gives remainder $1$, so $\text{LCM}[2,3,4,5,6,7]$ should also give remainder 1. Therefore, answer is $420-1=419$.

How does this work? Is this even correct?

Note that the Chinese remainder theorem requires that the $n_i$'s are pairwise coprime, which is not satisfied here. Note that $x $ leaves a remainder of $-1$ in each case, so just take the LCM of the numbers $2$ to $7$ and subtracting $1$ should give you the correct answer. — , Dec 09 '17 at 06:49

score 1 · Accepted Answer · answered Dec 09 '17 at 06:48

1

The idea is to rewrite the congruences as $$x\equiv-1\bmod2,3,4,5,6,7$$ and it is now clear that the solutions are $-1+\operatorname{lcm}(2,3,4,5,6,7)k$ for $k\in\mathbb Z$. Therefore the smallest positive solution is 419, as the teacher derived.

answered Dec 09 '17 at 06:48

Parcly Taxel

103,344

How do I use the ChineseRT? EG if it were $x\equiv5\pmod7$, or similar? – DynamoBlaze Dec 09 '17 at 06:50
@MalayTheDynamo Here, the solution is so obvious that the CRT isn't even needed. For general problems, the idea with the CRT is to start with one congruence and add other congruences to it, building up the answer as you go. – Parcly Taxel Dec 09 '17 at 06:51
Do you know of an answer (or question) where this is explained? – DynamoBlaze Dec 09 '17 at 06:51
@MalayTheDynamo The answers here may be of help. – Parcly Taxel Dec 09 '17 at 06:53
My thanks. the answers are varied. I think my understanding of the CRT ust went up by 50% – DynamoBlaze Dec 09 '17 at 07:02
Oh, of course. Got distracted by those answers. – DynamoBlaze Dec 09 '17 at 07:13

Series of Equivalences

1 Answers1