Question

Show that if a, b and c are integers with c | ab, then c| (a,c)(b, c)
Please, help

Answer 1

It is easy to prove by usual way:
(a, c ) = xa + yc for some x, y in Z
(b, c) = sb + tc for some s, t in Z
(a,c) (b,c) = (xa + yc)(sb + tc)
= xasb + xatc + ycsb + yctc
= ab(xs) + c ( atx ) + c (ysb) + c ( ytc)
c | ab for the first term , hence c divide the sum.
Problem is : my Prof wants me to use prime factorization to prove it.

Answer 2

My attempt:
\(c = \prod p_i^{m_i}\)

\(ab= \prod p_i^{s_i}\)
\(c|ab \implies m_i < s_i\)
Then, no where to go. :(

Answer 3

@ganeshie8

Answer 4

I've only tried the easy way...interesting how you would use it for prime factorisation

Answer 5

I don't get why c | ab, implies \(c_i \geq a_i + b_i\)

Answer 6

Oops, it is a typo, fixed here :
Let :
\(a = \prod p_i^{a_i}\)
\(b = \prod p_i^{b_i}\)
\(c = \prod p_i^{c_i}\)


then,
\((a,c) = \prod p_i^{\min\{a_i,c_i\}}\)
\((b,c) = \prod p_i^{\min\{b_i,c_i\}}\)

\(c\mid ab \implies c_i \le a_i+b_i\)

so, \(\min\{a_i,c_i\}+\min\{b_i,c_i\} \le a_i+b_i \ge c_i \blacksquare \)

Answer 7

Got you. Thank you so much.

Answer 8

np