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 $72n - 12$ 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 $2$s and $6$s.

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