Assume that (m,n)=1. Given integers a and b, prove that there exists an x such that x=a(modm) and x=b(modn)
Favorites|Homepage
Subscriptions | sitemap
HOME > Mathematics > Assume that (m,n)=1. Given integers a and b, prove that there exists an x such that x=a(modm) and x=b(modn)

Assume that (m,n)=1. Given integers a and b, prove that there exists an x such that x=a(modm) and x=b(modn)

[From: ] [author: ] [Date: 11-10-06] [Hit: ]
.. , n-1} mod n. you can prove this with contradiction: suppose a+cm is congruent to a+dm (mod n) where c and d are distinct and in {0, 1,......
we should assume that m, n > 0.

consider the set A = {a, a+m, a+2m, ... , a+(n-1)m}. since (m,n)=1 this set is congruent to B = {0, 1, ... , n-1} mod n. you can prove this with contradiction: suppose a+cm is congruent to a+dm (mod n) where c and d are distinct and in {0, 1, ... , n-1}. m has a multiplicative inverse mod n by bezout's, so our congruence

a+cm is congruent to a+dm (mod n)

is directly manipulated into

c is congruent to d (mod n)

contradiction.

finally since |A| = n and there are only n possible residue classes mod n, every class must be represented in A, and in particular [b] is represented.

EDIT: i think this way is easier. i looked up unicode ≡ for ease of reading. let's rewrite x ≡ a (mod m) as x = a+my. so we wish to find integer y such that a+my ≡ b (mod n). change to my ≡ b-a (mod n), and further, y ≡ (b-a)*m^(-1) (mod n). there we have it. again we need (m,n) = 1 for existence of m^(-1) (mod n).

-
ummm i dont think anyone would be able to answer that in this site but good luck
:)
1
keywords: and,an,that,1.,modn,Assume,Given,there,prove,such,modm,integers,exists,Assume that (m,n)=1. Given integers a and b, prove that there exists an x such that x=a(modm) and x=b(modn)
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .