Hi, I'm having a few problems with a math question and I'm hoping someone here can help me..?

Question

The question is:
Let c and d be divisors of n. If (c,d) = 1 then cd|n.
I have to prove that cd|n and I'm not really sure how to go about that. Any help would be greatly appreciated.

To the other person that replied, I don't understand your notation, what's with the % and everything?

Answer 1

Let c and d be divisors of n . Then:

(1%n) = (1%n) * (c+d)%(c+d)
(1%n) = (1%n) * (c%c+d) + (d%c+d)
(1%n) = ((1%n) * c%c+d) + ((1%n) * d%c+d)
(1%n) = (1%(n%c)*c+d) + (1%(n%d)*c+d)
Since c and d are divisors of n , n%c and n%d are integers and so are (n%c)*c+d and (n%d)*c+d , with the latter two the x and y that we seek. To avoid duplicates, we choose c and d to satisfy c<:d and 1=c+.d .

div is from the divisors page; div n are all the divisors of n .

div=: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)

cd=: 3 : 0
(,(<:/~d)*.1=+./~d) # ,/,"0/~d=. div x: y
)

ufs2=: 3 : 0
n=. x: y
z=. % n (% * +/"1@]) cd n
assert. ~: z
assert. (%n) = +/"1 z
assert. (=<.) %z
)

ufs2 12
1r24 1r24
1r36 1r18
1r48 1r16
1r60 1r15
1r84 1r14
1r156 1r13
1r30 1r20
1r28 1r21
r,s and c,d are related as follows:

(% +./"1) n + rs n NB. c,d from r,s
n -~ n (% * +/"1@]) cd n NB. r,s from c,d

Hope this helps.

Answer 2

Sorry this will be a bit patchy but you should be able to make it more rigorous.

Since c is a divisor of n then n=cx for some integer x
Since d is a divisor of n then n=dy for some integer y

cd has a unique prime factorisation. Because of the above c can be made up of some of the factors. d can be made up of completely different factors as (c,d)=1

so n = cdz

Where z is the remaining unused factors

so cd is a divisor of n

Answer 3

Here is a proof of Euclid's lemma, which is VERY close to yours! It should help you formulate your proof!
http://en.wikipedia.org/wiki/Euclid%27s_lemma