1
$\begingroup$

How to approach this problem:

N is the least number such that $N \equiv 7 \mod 180$ or $N \equiv 7 \mod 144$ but $N \equiv 1 \mod 7$.Then which of the these is true:

  1. $0 \lt N \lt 1000$
  2. $1000 \lt N \lt 2000$
  3. $2000 \lt N \lt 4000$
  4. $N \gt 4000$

Please explain your idea.

ADDED: The actual problem which comes in my paper is "or" and the "and" was my mistake but I think I learned something new owing to that.Thanks all for being patient,and appologies for the inconvenience.

  • 0
    @Tretwick See the simpler solution I added to my answer.2011-07-13

3 Answers 3

6

(1) For the original version of the question $\rm\:mod\ 180 \ $ and $\rm\: mod\ 144\::$

$\rm\: 144,\:180\ |\ N-7\ \Rightarrow\ 720 = lcm(144,180)\ |\ N-7\:.\:$

So, $\rm\: mod\ 7:\ 1\equiv N = 7 + 720\ k\ \equiv -k\:,\:$ so $\rm\:k\equiv -1\equiv 6\:.$

Thus $\rm\: N = 7 + 720\ (6 + 7\ j) =\: 4327 + 5040\ j\:,\:$ so $\rm\ N\ge0\ \Rightarrow\ N \ge 4327\:.$

(2) For the updated simpler version $\rm\:mod\ 180\ $ or $\rm\ mod\ 144\:,\:$ the same method shows that

$\rm\: N = 7 + 180\ (3+ 7\ j)\:$ or $\rm\:N = 7 + 144\ (2 + 7\ j)\:,\:$ so the least\rm\ N> 0\: is $\rm\:7 + 144\cdot 2 = 295\:.$

SIMPLER $\rm\ N = 7+144\ k\equiv 4\ k\ (mod\ 7)\:$ assumes every value $\rm\:mod\ 7\:$ for $\rm\:k = 0,1,2,\:\cdots,6\:,\:$ and all these values satisfy $\rm\:0 < N < 1000\:.\:$ Presumably this is the intended "quick" solution.

  • 0
    $\quad$Aha,lovely! :)2011-07-13
3

The title says "or" and the text says "and". I will assume "and".

We want $N$ to be congruent to $7$ modulo $180$ and modulo $144$. This will be true iff $N$ is congruent to $7$ modulo the LCM of $180$ and $144$, which is $720$.

So $N$ must have shape $N=720k+7$ for some integer $k$.

But we want $N \equiv 1 \pmod{7}$.

Since $N=700k +20k +7$, we can see that $N\equiv 20k \pmod{7}$.

Presumably we want $N$ positive, though this was not specified. It is easy to see that the least positive $k$ that works is $k=6$. Why is it so easy? Note that $20\equiv -1 \pmod{7}$. So to make $20k \equiv 1 \pmod{7}$, we must have $k \equiv -1\pmod{7}$. The least positive $k$ congruent to $-1$ is $6$.

That forces $N>4000$.

Added: The text of the original question said $180$ and $144$.

For the "or" version, we note that $N \equiv 7 \pmod{\gcd(180,140)}$.

Thus $N\equiv 7 \pmod{36}$, or equivalently $N$ is of the shape $36k+7$. In particular, since $N \equiv 1 \pmod 7$, we must have $k\equiv 1 \pmod 7$. Probably at this stage (or earlier!) search is most efficient. Try $k=8$. That gives $N=295$, which works, since $295=(2)(144)+7$.

2

I assume that the question is "or." Then it is simplest to just compute the answer.

Notice that $180 \equiv 5 \pmod{7}$ and $144\equiv 4 \pmod{7}$. Since $3\cdot 5\equiv 1\pmod 7$, we see that $3\cdot 180+7\equiv 1\pmod{7}$. Also, since $2\cdot4\equiv 1\pmod{7}$ we also have $2\cdot144 +7\equiv 1\pmod{7}$. As the smaller of the two is the second, we conclude that $N=295$.

  • 1
    @use Actually the "or" case can be done more simply, see the "simpler" update to my answer.2011-07-13