Congruence

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
Find the in-congruent solutions to \(\displaystyle 49x\equiv 22 \ \mbox{(mod 36)}\)

\(\displaystyle gcd(36,49)=1\)
\(\displaystyle 49=36*1+13\)
\(\displaystyle 36=13*2+10\)
\(\displaystyle 13=10*1+3\)
\(\displaystyle 10=3*3+1\)
\(\displaystyle 3=1*3+0\)
Working backwards I obtain: \(\displaystyle 1=36*15-49*11\)

\(\displaystyle -11\equiv y \ \mobx{(mod 36)}\rightarrow -11\equiv 25 \ \mbox{(mod 36)}\)

\(\displaystyle x\equiv 22*25 \ \mbox{(mod 36)}\rightarrow x\equiv 10 \ \mbox{(mod 36)}\)

\(\displaystyle x_0=10\)

\(\displaystyle x=10+36t \ 0\leq t<1\)
\(\displaystyle x=10 \ \mbox{is the in-congruent solution}\)

Is this correct and if so, is there an easier way to do this?
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
It is easy to see that it works: 49*10= 490 and 490/36= 13 with remainder 22.

As for an "easier way", what you did looks pretty easy to me! Certainly better than multiplying 48 by 1, 2, 3, etc. until you find the right one.
 

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
It is easy to see that it works: 49*10= 490 and 490/36= 13 with remainder 22.

As for an "easier way", what you did looks pretty easy to me! Certainly better than multiplying 48 by 1, 2, 3, etc. until you find the right one.
Maybe easy is the wrong word. Is there a more efficient way?
 
Dec 2009
1,506
434
Russia
Maybe...

49x=22(mod 36)

==>

49x+14=36=0 (mod36)

==>

7(7x+2)=0(mod36)

now it's clear that x=10
 
Jun 2010
148
110
Israel
Find the in-congruent solutions to \(\displaystyle 49x\equiv 22 \ \mbox{(mod 36)}\)

\(\displaystyle gcd(36,49)=1\)
\(\displaystyle 49=36*1+13\)
\(\displaystyle 36=13*2+10\)
\(\displaystyle 13=10*1+3\)
\(\displaystyle 10=3*3+1\)
\(\displaystyle 3=1*3+0\)
Working backwards I obtain: \(\displaystyle 1=36*15-49*11\)

\(\displaystyle -11\equiv y \ \mobx{(mod 36)}\rightarrow -11\equiv 25 \ \mbox{(mod 36)}\)

\(\displaystyle x\equiv 22*25 \ \mbox{(mod 36)}\rightarrow x\equiv 10 \ \mbox{(mod 36)}\)

\(\displaystyle x_0=10\)

\(\displaystyle x=10+36t \ 0\leq t<1\)
\(\displaystyle x=10 \ \mbox{is the in-congruent solution}\)

Is this correct and if so, is there an easier way to do this?
In general, the congruence \(\displaystyle ax\equiv b(mod\ n)\) has solutions if and only if \(\displaystyle gcd(a,n)|b\). In case solutions exist, there are exactly \(\displaystyle gcd(a,n)\) incongruent solutions modulo \(\displaystyle n \).


\(\displaystyle 49x\equiv 22\equiv -14(mod\ 36)\) and since \(\displaystyle gcd(7,36)=1\) you can cancel without affecting the modulus, then \(\displaystyle 7x\equiv -2(mod\ 36)\); multiply by \(\displaystyle -5 \), then \(\displaystyle -35x\equiv 10(mod 36)\); and the unique solution is \(\displaystyle x\equiv 10(mod\ 36)\).
 

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, dwsmith!

Here is a very primitive solution . . .


Solve:. . \(\displaystyle 49x \:\equiv\: 22 \text{ (mod 36)}\)

The congruence reduces to: .\(\displaystyle 13x \:\equiv\:22\text{ (mod 36)}\)

This means: .\(\displaystyle 13x \:=\:36a + 22\,\text{ for some integer }a.\)

\(\displaystyle \text{Solve for }x\!:\;\;x \:=\:\dfrac{36a + 22}{13} \:=\:2a + 1 + \dfrac{10a + 9}{13}\) .[1]

Since \(\displaystyle x\) is an integer, \(\displaystyle 10a + 9\) must be divisible by 13.

We have: .\(\displaystyle 10a + 9 \:=\:13b\,\text{ for some integer } b.\)

\(\displaystyle \text{Solve for }a\!:\;\;a \:=\:\dfrac{13b - 9}{10} \:=\:b + \dfrac{3b-9}{10}\) .[2]

Since \(\displaystyle a\) is an integer, \(\displaystyle 3b-9\) must be divisible by 10.

The first time this happens is when \(\displaystyle b = 3.\)


Substitute into [2]: .\(\displaystyle a \:=\:3 + \frac{3(3)-9}{10} \quad\Rightarrow\quad a = 3\)

Substitute into [1]: .\(\displaystyle x \;=\;2(3)+1 + \frac{10(3) + 9}{13} \quad\Rightarrow\quad x \:=\:10\)


Therefore: .\(\displaystyle x \:\equiv\:10\text{ (mod 36)}\)
 

simplependulum

MHF Hall of Honor
Jan 2009
715
427
Or how about this ?

\(\displaystyle 13x \equiv 2 \cdot 11 \bmod{36} \)

\(\displaystyle x \equiv 2 ~ \frac{ a - 1 }{a+1} ~~,~ a \equiv 12 \)

\(\displaystyle x \equiv 2 (a-1)( 1 - a + a^2 - a^3 + ... ) \)

I don't consider the convergence of the series because we find that \(\displaystyle a^n \equiv 0 ~,~ n \geq 2 \)

\(\displaystyle x \equiv 2(a-1)(1-a) \equiv 2( -a^2 + 2a - 1 ) \equiv 2(2a - 1 ) \equiv 2(23) \equiv 10 \)