Friday, 26 September 2014

elementary number theory - How do I change to a different modulo?

I'm trying to solve the following problem:




What remainder does integer n have when divided by 142 if we know that 20n+4 and 72n12 have the same remainder when divided by 142?





I 'translated' the problem to maths:



20n + 4 \equiv 72n - 12 \pmod {142} \\ n \equiv x \pmod {142}



And we are essentially looking for x. Solving the linear congruence on top:




20 + 4 \equiv 72n - 12 \pmod {142} \\ 52n \equiv 16 \pmod {142} \\ 13n \equiv 4 \pmod {71} \\ 13n \equiv 4 + 8 \times 71 \pmod {71} \\ 13n \equiv 572 \pmod {71} \\ n \equiv 44 \pmod {71} \\




So n = 71k + 44 for any k \in \mathbb{Z}.



The problem is that I can't answer the original question as there, the modulo is 142 and now it is 71. How could I somehow 'change' the modulo and get the right answer? Or what would be a way to think about this problem?



PS: I realise that I'll get more solutions. For example, if I had 2x \equiv 4 \pmod 8, I would divide by 2 and get x \equiv 2 \pmod 4. Then x = 4k + 2. For these numbers are for example 6, 9, 11, \ldots. I can see that if we were dividing these by 8, not 4, the remainders would be 2s and 6s.

No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...