Question

Find the smallest positive N such that("==" means congruent).
N==6(mod12)
N==6(mod18)
N==6(mod24)
N==6(mod30)
N==6(mod60)

Answer 1

http://www.math.cornell.edu/~putnam/modular.pdf

Answer 2

Hi, my understanding is that if I tke last two congruences, I get:
30a+6=60b+6, which simplifies to 30a + 60 b so when I get Mod30 by guess and check I get 0 mod30
Is my Ans correct?

Answer 3

simply take LCM of moduli and add 6

Answer 4

Well... We can say that:
$$
a \equiv b \mod n \implies a-b = 0 \mod n
$$Which means that \(n\) divides \(a-b\)
So those turn into:
$$
N \equiv 6 \mod 12 \implies N - 6 \equiv 0 \mod 12 \\
N \equiv 6 \mod 18 \implies N - 6 \equiv 0 \mod 18 \\
N \equiv 6 \mod 24 \implies N - 6 \equiv 0 \mod 24 \\
N \equiv 6 \mod 30 \implies N - 6 \equiv 0 \mod 30 \\
N \equiv 6 \mod 60 \implies N - 6 \equiv 0 \mod 60
$$Which means that \(N-6\) has to be a number that 12, 18, 24, 30 and 60 divide.
So to find it our work is similar to finding the `Least common multiple` of numbers:
http://en.wikipedia.org/wiki/Least_common_multiple

And we can do it by prime factorization (as described there as well).
$$
12 = 3 \cdot 2 \cdot 2 \qquad 18 = 3 \cdot 3 \cdot 2 \\
24 = 3 \cdot 2 \cdot 2 \cdot 2 \quad 30 = 3 \cdot 5 \cdot 2 \\
60 = 3 \cdot 5 \cdot 2 \cdot 2 \\
$$So we get that \(N-6\) has to be multiply of 360 in order to divide all these numbers:
$$
N-6 = k\cdot(2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5) = k \cdot 360\\
N = k \cdot 360 + 6
$$By setting \(k=0\) we get \(N=6\) which is the smallest positive number that makes it work.. but that is the trivial solution.. In case you need something more interesting you can try \(k=1 \implies N=366\)

Answer 5

\(\large \begin{aligned} \color{black}{

x\equiv 6\pmod {360}

}\end{aligned}\)

Answer 6

but 366 is not the correct answer

Answer 7

it is.

http://www.wolframalpha.com/input/?i=solve+n+mod+12%3D6%2Cn+mod+18%3D6%2Cn+mod+24%3D6%2Cn+mod+30%3D6%2Cn+mod+60%3D6+over+integers

Answer 8

oh wait it should be simply \(\Large 6\) then.

Answer 9

366 is the smallest positive integer

Answer 10

6! I got it! in the second try, lost 2 points... thanks!

Answer 11

but 6 is also the remainder when divided by such numbers , so i think ir should be 6

Answer 12

ahh k=0, 360k + 6 = 6 will do !

Answer 13

so actually it was an observation question

Answer 14

I know, but the funny thing is that for N=6 no work should be done really. it's the instant answer because 6 is smaller than all of the other numbers 12, 18, 24, 30, 60... so its modulo is the same for all

Answer 15

Because the moduli are not relatively prime, we do not have general algebraic tools to approach this problem. However, we can see by inspection that 6 clearly satisfies all five of the congruences and that no positive integer less than 6 could satisfy them

Answer 16

a | 0

any number divides 0.. yeah its more of an observation q

Answer 17

"the smallest positive N"

Answer 18

thank you! mathmath333 and ganeshie8 and pitamar!