Thursday 31 August 2017

elementary number theory - Find all integer solutions to linear congruences



Find all integer solutions to linear congruences:



\begin{align}
&(a) &3x &\equiv 24 \pmod{6},\\
&(b) &10x &\equiv 18 \pmod{25},\\

\end{align}



What I have so far:



$$(a) \gcd(3,6)=3$$
And we know $3|24$ so there are $3$ solutions. By inspection we know that $x=8$ is a solution.



One, question I have is, even though $x=8$ is a solution, I can also see that $x=2$ is a solution, and among others. Does it matter which I choose, or do I randomly choose a solution I see? From here I'm a tad confused. I'm missing something very simple.



$$(b) \gcd (10,25)=5$$




And $5 \nmid 18$ so there are no solutions. Right?


Answer



Using this, $(10,25)=5$ must divide $9$ to admit any solution, which is not, so there is no solution.



$3x\equiv 24\pmod 6\implies 2\mid x$ i.e., any even value(not only $8$) of $x$ will satisfy the 1st congruence.



So, the system of the linear congruence has no solution as the 2nd congruence is not solvable.







Alternatively, for the 2nd congruence, $10x-18=25y$ for some integer $y$,



So,$5(2x-5y)=18, \frac{18}5=2x-5y$ which is an integer, hence contradiction.


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