Congruence Theorem in Modular arithmetic and Euclid's lemma

• May 28th 2009, 10:07 AM
Coach
Congruence Theorem in Modular arithmetic and Euclid's lemma
Dear forum members,

I am currently doing a maths project and as a part of this project I am trying to prove a certain conjecture about the divisibility of numbers.

First of all, could someone please take a look at the proof given in this document on page 4, solution 2.

http://www.rowan.edu/open/depts/math...al+Version.pdf

I do not understand how does Euclid's lemma relate to the proof given, and I'd be grateful if someone could explain this to me.

Second, if I was trying to prove a certain thing about the divisibility of two integers, call them a and b, by a number x, and if I knew that the difference of these integers, a-b, is divisible by x, could I use the congruence theorem of modular arithmetic to prove that both a and b are divisible by x?

I am really lost in the world of proofs and do not understand them at all. So if someone could please help me, I would be very grateful.

Thank you!