Chinese Remainder Theorem without GDC=1

59 Views Asked by At

I was looking at this problem: The smallest positive integer greater than 1 that leaves a remainder of 1 when divided by 4, 5, and 6 lies between which of the following pairs of numbers? I was wondering if you could solve this using Chinese Remainder Theorem, I am new to using Chinese Remainder Theorem but I'm fairly certain you need the GDC for all mods equal to 1 and clearly GDC(4,6)=2, so I don't know what to do.

1

There are 1 best solutions below

1
On

If $x$ is $1$ more than a multiple of $4$, and of $5$, and of $6$, then it is $1$ more than a multiple of their least common multiple (LCM).