S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Wed, 19 Jun 2013 11:10:45 UTC

View unanswered posts | View active topics


Board index » Advanced Mathematics » Foundations

All times are UTC [ DST ]



Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ] 
  Print view Previous topic | Next topic 
Author Message
DgrayMan
 Post subject: Conrguence (integers modulo m)
PostPosted: Thu, 26 Apr 2012 17:39:22 UTC 
Offline
S.O.S. Oldtimer
User avatar

Joined: Sat, 21 Jan 2012 03:59:22 UTC
Posts: 182
If i have two equations ,

11a+b(mod26)=17
&
22a+b(mod26)=22


How do i begin to solve for a and b?
Top
 Profile  
 
Shadow
 Post subject: Re: Conrguence (integers modulo m)
PostPosted: Thu, 26 Apr 2012 20:27:29 UTC 
Offline
Moderator
User avatar

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12170
Location: Austin, TX
DgrayMan wrote:
If i have two equations ,

11a+b(mod26)=17
&
22a+b(mod26)=22


How do i begin to solve for a and b?


Use the Chinese remainder theorem.

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination
Top
 Profile  
 
DgrayMan
 Post subject: Re: Conrguence (integers modulo m)
PostPosted: Thu, 26 Apr 2012 22:37:38 UTC 
Offline
S.O.S. Oldtimer
User avatar

Joined: Sat, 21 Jan 2012 03:59:22 UTC
Posts: 182
at first i thought you were messing with me lol
Top
 Profile  
 
outermeasure
 Post subject: Re: Conrguence (integers modulo m)
PostPosted: Fri, 27 Apr 2012 05:25:17 UTC 
Online
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6066
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Shadow wrote:
DgrayMan wrote:
If i have two equations ,

11a+b(mod26)=17
&
22a+b(mod26)=22


How do i begin to solve for a and b?


Use the Chinese remainder theorem.


I assume the OP means 11a+b\equiv 17\pmod{26} etc. Why apply CRT here instead of eliminating a immediately?

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
Soroban
 Post subject: Re: Conrguence (integers modulo m)
PostPosted: Fri, 4 May 2012 17:52:27 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Mon, 19 May 2003 19:55:19 UTC
Posts: 7961
Location: Lexington, MA
Hello, DgrayMan!

Quote:
\text{Solve: }\:\begin{array}{cccc} 11a+b & \equiv & 17 \text{ (mod 26)} & [1] \\ 22a+b&\equiv& 22\text{ (mod 26)} & [2] \end{array}

\begin{array}{cccccccc}\text{Multiply [1] by 2:} & 22a + 2b &\equiv & 34\text{ (mod 26)} \\ \text{Multiply [2] by -1:} & \text{-}22a - b &\equiv& -22\text{ (mod 26)} \end{array}

. . \text{Add: }\:b\:\equiv\:12\text{ (mod 26)}


\text{Substitute into [1]: }\:11a + 12 \:\equiv\:17\text{ (mod 26)}

. . . . . . . . . . . . . . . . . . . .11a \:\equiv\:5\text{ (mod 26)}

\text{Multiply by 19: }\qquad\, 19\cdot11a \:\equiv \:19\cdot5\text{ (mod 26)} .**

n . . . . . . . . . . . . . . . . . .209a \:\equiv\:95\text{ (mod 26)}

. . . . . . . . . . . . . . . . . . . . . .a \:\equiv\:17\text{ (mod 26)}


\text{Solution: }\;\begin{Bmatrix}a & \equiv & 17 \text{ (mod 26)} \\ b & \equiv & 12 \text{ (mod 26)} \end{Bmatrix}


~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

**

How do we find that "19"?
Here is a primitive method . . .


We want to find x so that: .11x \:\equiv\:1\text{ (mod 26)}

That is: .11x \:=\:26m + 1

. . Then: .x \:=\:\dfrac{26m+1}{11} \quad\Rightarrow\quad x \:=\:2m + \dfrac{4m+1}{11}\;\;(a)

Since x is an integer, 4m+1 must be a multiple of 11: .4m+1 \:=\:11n

We have: .m \:=\:\dfrac{11n-1}{4} \quad\Rightarrow\quad m \:=\:2n + \dfrac{3n-1}{4}\;\;(b)

Since m is an integer, 3n-1 must be a multiple of 4: .3n-1 \:=\:4p

We have: .n \:=\:\dfrac{4p+1}{3}

By inspection, we find p = 2 \quad\Rightarrow\quad n = 3

Substitute into (b): .m \:=\:2(3) + \dfrac{3(3)-1}{4} \quad\Rightarrow\quad m = 8

Substitute into (a): .x \:=\:2(8) + \dfrac{4(8) + 1}{11} \quad\Rightarrow\quad x \,=\,19


And that is how I found the multiplicative inverse of 11, mod 26.
Top
 Profile  
 
outermeasure
 Post subject: Re: Conrguence (integers modulo m)
PostPosted: Sat, 5 May 2012 05:39:56 UTC 
Online
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6066
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Soroban wrote:
And that is how I found the multiplicative inverse of 11, mod 26.


Why do it the hard way when you could just use Bezout/Euclid?

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ] 

Board index » Advanced Mathematics » Foundations

All times are UTC [ DST ]

Who is online

Users browsing this forum: No registered users

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA