Chinese Remainder Theorem


by chaotixmonjuish
Tags: chinese, remainder, theorem
chaotixmonjuish
chaotixmonjuish is offline
#1
Apr10-08, 09:00 PM
P: 287
I need help making sense of my notes:

x congruent 4 mod 11
x congruent 3 mod 13

ai mi Mi yi aiMiyi
4 11 13 6 4*13*6
3 13 11 6 3*11*6

I'm not sure where the six came from
Phys.Org News Partner Science news on Phys.org
Review: With Galaxy S5, Samsung proves less can be more
Making graphene in your kitchen
Study casts doubt on climate benefit of biofuels from corn residue
lurflurf
lurflurf is offline
#2
Apr11-08, 12:21 AM
HW Helper
P: 2,155
no clue
usually one solves
13a=4 (mod 11) (a=0,1,...10)
11b=3 (mod 13) (b=0,1,...12)
ie a and be are found by modular division
so that
n*gcd(11,13)+(gcd(11,13)-13a-11b)
with n=1,2,3,...
solves the original problem
robert Ihnot
robert Ihnot is offline
#3
Apr11-08, 02:27 AM
PF Gold
P: 1,059
Chaotixmonjuist:
ai mi Mi yi aiMiyi
4 11 13 6 4*13*6
3 13 11 6 3*11*6 I'm not sure where the six came from

Some number repeats are going on there. But we have 1/11==6 Mod 13, and 1/13==6 Mod 11.

robert Ihnot
robert Ihnot is offline
#4
Apr21-08, 11:48 AM
PF Gold
P: 1,059

Chinese Remainder Theorem


I was hoping someone would go a little further with this problem. It may not be clear what is being discussed. (Apparently the teacher must have been writing on the blackboard.)

What I take is being said above is X==4 Mod 11 and X==3 Mod 13. Find X congruent to 11x13= 143.

Setting up the first part of the problem, we want to find 4/13 ==X(1) Mod 11, and 3/11==X(2) Mod 13.

The first case gives x(1)==24==2 Mod 11, and the second gives X(2) ==18==5 Mod 13. So we get x(1)=2, X(2)=5.

We then set up the equation X =13*x(1) + 11*x(2) +k143. (k is chosen so as to give us the smallest positive value.)

Now if we checked this product Mod 11 the last part on x(2) would go out. On the other hand on the first part, 13*x(1), we have included the inverse of 13 mod 11 in our calcuations, so we are only going to get the value of X ==4 Mod 11. Similarly for the other part of the equation.

So that working out the equation: X=13*2 + 11*5 = 81. This value satisfies the conditions.


Register to reply

Related Discussions
Chinese Remainder Theorem!!! Linear & Abstract Algebra 5
Number Theory: Inverse of 0 mod n? Chinese Remainder Theorem Calculus & Beyond Homework 5
The remainder theorem Precalculus Mathematics Homework 2
remainder theorem Calculus 2
inverse chinese remainder theorem Linear & Abstract Algebra 9