若a,b,c,d是整數,已知ac,bc+ad和bd有公因數e,問bc和ad是否也有公因數e?

(1) 設 e = p 是質數.

因 p|ac 故 p|a or p|c;
同理 p|b or p|d.

若 (p|a 且 p|c) 或 (p|b 且 p|d),
顯然 p|ad 且 p|bc.

若 (p|a 且 p|d) 或 (p|b 且 p|c),
則 p|ad 或 p|bc.
但因 p 是其和的因數, 另一項自然也可被 p 整除.

顯然若有  (e|a or e|c) 且 (e|b or e|d),
即使 e 是合數, 結論也是成立的.


(2) 考慮 e = p^t 的情形, p 是質數.

設 a = Ap^m, b = Bp^n, c = Cp^r, d = Dp^s.
m, n, r, s 為非負整數, 而 A, B, C, D 皆無 p 之因數.
則在 e|ac, e|bd 條件下, m+r≧t, n+s≧t.
則 ad = ADp^(m+s), bc = BCp^(n+r)
其中 m+s, n+r 至少有一者在 t 以上,
也就是說 ad, bc 至少一項是 e = p^t 的倍數.
但 e|ad+bc, 所以 e|ad 且 e|bc.


(3) 現在考慮一般情形: 把 e 做質因數分解
    e = p_1^(t_1)．．．p_m^(t_m).

e|(ac,bd,ad+bc)
    ==> p_i^(t_i)|(ac,bd,ad+bc), for all i
    ==> p_i^(t_i)|(ad,bc), for all i
    ==> e|(ad,bc)

Q.E.D.