# How to find the least $N$ such that $N \equiv 7 \mod 180$ or $N \equiv 7 \mod 144$ but $N \equiv 1 \mod 7$?

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$

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.

-
There is no least such number, since if $N$ satisfies these congruences, then $N - 180 \cdot 144 \cdot 7$ does so too. – Alexander Thumm Jul 13 '11 at 18:34
@AlexanderThumm Since the cases only concern positive numbers, let's assume that's what he means by number. – kba Jul 13 '11 at 18:37
@Tretwick See the simpler solution I added to my answer. – Bill Dubuque Jul 13 '11 at 19:38

(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.

-
+1, Since this is a complete answer to the original. (I am not sure which he wants?) – Eric Naslund Jul 13 '11 at 19:03
$\quad$Aha,lovely! :) – Quixotic Jul 13 '11 at 19:46

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

-
+1 for you too. – Eric Naslund Jul 13 '11 at 19:03
+1,nice explanation. – Quixotic Jul 13 '11 at 19:17

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 also, reciprocation. In this case the change is not a big issue, since the investment in producing an answer for either version is minimal. – André Nicolas Jul 13 '11 at 19:20
@use Actually the "or" case can be done more simply, see the "simpler" update to my answer. – Bill Dubuque Jul 13 '11 at 19:46