Suppose p and q are any two distinct numbers such that gcd(p, q) = 1...?

2009-03-26 4:04 pm
Suppose p and q are any two distinct numbers such that gcd(p, q) = 1.
(i) Suppose a number is divisible by p and q. Prove that this number is also divisible by pq.
(ii) Let a be any number. Then solving x = a (mod pq) is the same as solving the following equations:

x = a (mod p)
x = a (mod q)

回答 (1)

2009-03-27 2:35 am
✔ 最佳答案
From the extended euclidean algorithm, as gcd(p,q) = 1 you know there are integers a and b for which ap + bq = 1.

(i) Multiplying both sides by n we conclude napn + nbq = n.

Since p and q each divide n there are integers r, s with n = pr and n = qs. Substituting into the equation of the previous paragraph we see (qs)ap + (pr)bq = n. Thus n = (pq) (sa + br) is an integer multiple of pq.

(ii) Suppose x = a (mod p) and x = a (mod q); by definition, this means x-a is a multiple of p and x-a is a multiple of q. By (i) (with x-a playing the role of "a number") we conclude that x-a is a multiple of pq, and thus x = a (mod pq) by definition.

Suppose conversely that x = a (mod pq). This means by definition that x - a is an integer multiple of pq. Since an integer multiple of pq is also an integer multiple of p, x = a (mod p) follows by definition; since an integer multiple of pq is also an integer multiple of q, x = a (mod q) follows by definition.

I can understand getting stuck on (ii); being asked to show that "solving" one equation is "the same as" solving a system of equations is a somewhat vague instruction. What it means is to show that any solution to the one equation is a solution to the system, and vice versa. (This does have as a logical consequence that any method of dealing with equation will produce the same results as any method of dealing with the system.)

When gcd(p, q) is not 1, it is still true that any solution to x = a (mod pq) is a solution to the system, but it is no longer necessarily true that a solution to the system is a solution to x = a (mod pq).


收錄日期: 2021-05-01 12:12:25
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20090326080453AAsX2Pd

檢視 Wayback Machine 備份