mersenneforum.org solving modular constraints
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2010-02-17, 20:07 #1 Joshua2     Sep 2004 53310 Posts solving modular constraints x = 1 mod 3 x = 2 mod 4 x = 3 mod 5 so I changed the numbers from my problem, but its similar. I'm trying to find what x could be. I'm pretty sure I can do LCM of 3,4,5 and know the answer is 60N + something or something mod 60. What's the best way to find out; for small problems it would seem try 8 then 13, and so on up to 60, is there a faster way for even small problems like this? I know there's fast ways using chinese remainder theorem; maybe someone could demonstrate a little algorithm on these numbers? Thanks!
2010-02-17, 20:51   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Joshua2 x = 1 mod 3 x = 2 mod 4 x = 3 mod 5 so I changed the numbers from my problem, but its similar. I'm trying to find what x could be. I know there's fast ways using chinese remainder theorem; !
??

You answered your own question. Use the CRT.

What else are you looking for? There are plenty of examples.

 2010-02-17, 20:55 #3 wblipp     "William" May 2003 New Haven 23×103 Posts (40 + 30 + 48) mod 3 = (1+0+0) (40 + 30 + 48) mod 4 = (0+2+0) (40 + 30 + 48) mod 5 = (0+0+3) so 40 + 30 + 48 = 118 works. As you have observed, any equivalent answer mod 60 will work. Depending on your needs, the smallest answer is either 58 or -2. As you seemed to already know, this is the Chinese Remainder Theorem. The trick is to make a sum so that all but one addend is zero for each modulo. I have difficulty imagining anything simpler. It's also more help than we ought to give in homework. I justify it on the grounds of your claim to have changed the numbers and the usefulness of a pedagogical example.
 2010-02-17, 20:56 #4 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts Rather than "trying" 3, 8, 13, etc., do it algebraically. If x = 3 mod 5, then x= 5A+3 for some integer A. Substituting in the other constraints 5A+3 = 1 mod 3 5A+3 = 2 mod 4 But this is the same as 2A = 1 mod 3 A = 3 mod 4 Thus, we have reduced the number of constraints. When we find permissible values for A, we can substitute and we will have the permissible values for x
2010-02-18, 07:56   #5
Joshua2

Sep 2004

13·41 Posts

Quote:
 Originally Posted by Wacky Rather than "trying" 3, 8, 13, etc., do it algebraically. If x = 3 mod 5, then x= 5A+3 for some integer A. Substituting in the other constraints 5A+3 = 1 mod 3 5A+3 = 2 mod 4 But this is the same as 2A = 1 mod 3 A = 3 mod 4 Thus, we have reduced the number of constraints. When we find permissible values for A, we can substitute and we will have the permissible values for x
This way makes a ton of sense. Is this the CRT as well? Its seems we can't continue with 2A = 1 + 3A and A = 3 + 4A? I think I did that wrong. How about A = 3 + 4B and 2A = 1 + 3 B with two equations and two unknowns? I'll look at the other posts more later.

2010-02-18, 13:04   #6
Wacky

Jun 2003
The Texas Hill Country

44116 Posts

Quote:
 Originally Posted by Joshua2 Is this the CRT as well?
Why don't you tell us? Is it, or is it not? Why?
Quote:
 Its seems we can't continue with 2A = 1 + 3A and A = 3 + 4A? I think I did that wrong.
A correct observation.
Quote:
 How about A = 3 + 4B and 2A = 1 + 3 B
That's the spirit
Quote:
 with two equations and two unknowns?
Is that what we did before?

 2010-02-19, 06:53 #7 Joshua2     Sep 2004 13·41 Posts 1. I don't think it is CRT, because I read that you use euclid's extended algorithm, and we didn't use it. 2. I think that is what we did before, reduce by one. A = -2 - B = 3 + 4B so -2 - 3 = 5B or -5 = 5B so B = -1. So is that the right idea?
2010-02-19, 06:56   #8
Joshua2

Sep 2004

13×41 Posts

Quote:
 Originally Posted by wblipp (40 + 30 + 48) mod 3 = (1+0+0) (40 + 30 + 48) mod 4 = (0+2+0) (40 + 30 + 48) mod 5 = (0+0+3) so 40 + 30 + 48 = 118 works.
Where did 40, 30 and 48 come from? I assume the 1+0+0 thing is prime factored?

2010-02-19, 08:04   #9
wblipp

"William"
May 2003
New Haven

23×103 Posts

Quote:
 Originally Posted by Joshua2 Where did 40, 30 and 48 come from?
CRT.
The first number needs to be a multiple of 4*5 that is 1 mod 3.
The second number needs to be a multiple of 3*5 that is 2 mod 4
The third number needs to be a multiple of 3*4 that is 3 mod 5

Quote:
 Originally Posted by Joshua2 I assume the 1+0+0 thing is prime factored?
(40 + 30 + 48) mod 3
=(40 mod 3) + (30 mod 3) + (48 mod 3)
= 1 + 0 + 0
=1

2010-02-19, 15:24   #10
Wacky

Jun 2003
The Texas Hill Country

32·112 Posts

Quote:
 Originally Posted by Joshua2 1. 2. I think that is what we did before, reduce by one. A = -2 - B = 3 + 4B so -2 - 3 = 5B or -5 = 5B so B = -1. So is that the right idea?
No. I think that you may be confusing the "algebraic equality" (as in X = 5 A + 3) with the "modular equality" (as in X = 3 mod 5).
They are somewhat different concepts. Therefore, for clarification, I will use "==" in the latter case.

We are reducing the number of constraints by one by making a substitution that causes one of the constraints to be met for all values of the unknown.

We started with:

Code:
Find the set of integers "X" such that

X == 1 mod 3
and
X == 2 mod 4
and
X == 3 mod 5
We made the substitution

X = 5 A + 3

This transformed the last constraint into

Code:
5 A + 3 == 3 mod 5
which is true for all integers A

That left us with the equivalent problem:

Code:
Find the set of integers "A" such that

5 A + 3 == 1 mod 3
and
5 A + 3 == 2 mod 4
or, equivalently:

Code:
Find the set of integers "A" such that

2 A == 1 mod 3
and
A == 3 mod 4
So, continuing this procedure:
We let A = 4 B + 3 which will meet the last constraint for all integers B, leaving only one constraint (mod 3).
Then we let B = 3 C + … (something), which will be true for all integers C.

Finally, we combine all of the substitutions to get one substitution
X = f(C), which meets all of the constraints for any integer C.

As you already know, from other posts, this will be
Code:
X = 60 C + 58
or equivalently,
Code:
X == 58 mod 60
However, you should work out the details to derive the answer yourself.
There are a couple of aspects of the derivation that might catch you unaware. You should also look to see similar coefficients in the CRT solution. Observing these similarities might give you a greater insight into "why the methods work"

Last fiddled with by Wacky on 2010-02-19 at 15:52 Reason: Formatting to clarify the presentation

2010-02-19, 21:10   #11
Joshua2

Sep 2004

53310 Posts

Quote:
 Originally Posted by wblipp CRT. The first number needs to be a multiple of 4*5 that is 1 mod 3. The second number needs to be a multiple of 3*5 that is 2 mod 4 The third number needs to be a multiple of 3*4 that is 3 mod 5 (40 + 30 + 48) mod 3=(40 mod 3) + (30 mod 3) + (48 mod 3) = 1 + 0 + 0 =1
I think I understand CRT now. Now I just need to figure out modulo inverses, like what is inverse of 2 mod 5...

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-11-04 16:53 paulunderwood Miscellaneous Math 17 2016-12-31 22:11 paulunderwood Miscellaneous Math 2 2016-12-30 07:34 Dubslow Miscellaneous Math 24 2012-08-24 10:46 flouran Math 4 2008-12-19 17:22

All times are UTC. The time now is 13:16.

Sat Jan 29 13:16:53 UTC 2022 up 190 days, 7:45, 1 user, load averages: 1.58, 1.64, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔