number theory

數學神童

请问谁可以教我怎样solve linear congruences 的题目？

a)find all integers x that satisfy the congruence

2x=0 （mod 6)

b)find all integers x and y that satisfy the pair of congruences

2x+y=1 (mod 6)
x+3y=3 (mod 6)

puangenlun

第一题答案应该是3的倍数

第二题就不知道了

antimatter

第二题的x 应该是6 的倍数。y 则是30 的倍数+1-2x。
或者
y 是6 的倍数+1，x 是30 的倍数+3-3y。

walrein_lim88

第二题的x 应该是6 的倍数。y 则是30 的倍数+1-2x。
或者
y 是6 的倍数+1，x 是30 的倍数+3-3y。
antimatter 发表于 22-2-2010 11:52 AM

    请SHOW WORKING来。。。。

~HeBe~_@

请问谁可以教我怎样solve linear congruences 的题目？

b)find all integers x and y that satisfy the pair of congruences

2x+y=1 (mod 6)
x+3y=3 (mod 6)

數學神童 发表于 20-2-2010 11:39 PM

2x + y = 1 (mod 6)  ----- (1)
x + 3y = 3 (mod 6)  ----- (2)

From (1), 6 (2x + y) = 6 (mod 6)
                12x + 6y = 0 (mod 6)

      2(x + 3y) + 10x = 0 (mod 6)
      
                  6 + 10x = 0 (mod 6)
                        10x = -6 (mod 6)            gcd (10, 6) = 2
                            x = 0 (mod 3)

Substitute (3) into (1) and (2),

From (1),  2(0) + y = 1 (mod 6)
                           y = 1 (mod 6)
                           y = ..., 1, 7, 13, ...

From (2),     0 + 3y = 3 (mod 6)  
                         3y = 3 (mod 6)            gcd (3, 6) = 3
                           y = 1 (mod 2)         
                           y = ..., 1, 3, 5, ...

Checking
If y = 7, x =0,        then     0 + 7 = 1 (mod 6)  ;    0 + 3(7) = 21 = 3 (mod 6) .
If y =  3, x = 0 ,     then     0 + 3 is not congruent to 1 (mod 6) ; 0 + 3(3) = 9=3 (mod 6)

Therefore, y = 1 (mod 6)      and   x = 0 (mod 3)

yw46

x+3y=3 (mod 6)

3y = 3 mod 6 or 0 mod 6
x不是0 mod 6就是 3 mod 6