Congruence

**dwsmith** · July 4th 2010, 09:54 AM

Find the in-congruent solutions to $49x\equiv 22 \ \mbox{(mod 36)}$

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

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

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

$x_0=10$

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

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

**HallsofIvy** · July 4th 2010, 12:31 PM

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** · July 4th 2010, 01:00 PM

Originally Posted by HallsofIvy

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?

**Also sprach Zarathustra** · July 4th 2010, 01:19 PM

Maybe...

49x=22(mod 36)

==>

49x+14=36=0 (mod36)

==>

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

now it's clear that x=10

**melese** · July 4th 2010, 02:20 PM

Originally Posted by dwsmith

Find the in-congruent solutions to $49x\equiv 22 \ \mbox{(mod 36)}$

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

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

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

$x_0=10$

$x=10+36t \ 0\leq t<1$
$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 $ax\equiv b(mod\ n)$ has solutions if and only if $gcd(a,n)|b$ . In case solutions exist, there are exactly $gcd(a,n)$ incongruent solutions modulo $n$ .

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

**Also sprach Zarathustra** · July 4th 2010, 02:22 PM

This is "my solution"

**melese** · July 4th 2010, 02:25 PM

Originally Posted by Also sprach Zarathustra

This is "my solution"

That's wonderful.

**Soroban** · July 4th 2010, 05:19 PM

Hello, dwsmith!

Here is a very primitive solution . . .

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

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

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

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

Since $x$ is an integer, $10a + 9$ must be divisible by 13.

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

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

Since $a$ is an integer, $3b-9$ must be divisible by 10.

The first time this happens is when $b = 3.$

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

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

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

**simplependulum** · July 4th 2010, 07:43 PM

Or how about this ?

$13x \equiv 2 \cdot 11 \bmod{36}$

$x \equiv 2 ~ \frac{ a - 1 }{a+1} ~~,~ a \equiv 12$

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

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

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

Thread: Congruence

LinkBack

Thread Tools

Display

Congruence

Similar Math Help Forum Discussions

Congruence

Congruence

congruence

Congruence

Congruence

Search Tags