# Congruence problem with gcd

• February 20th 2007, 07:52 PM
Congruence problem with gcd
1. Let d,k,n be integers with n>d>1. If d=gcd(k,n), prove there exist an integer e such that 1<e<n and ke congruence 0 (mod n).

My proof so far:

Now d > 1 implies d >= 2, n > d implies n>=3, therefore there exists a integer e such that n > e > 1 with e >=2.

Now I understand that I need to have something like ke = 0 + na for an integer a for the second part of the proof, now I seem to figure out.

I wrote stuff like k = dv and d = ki + nj for integer v,i,j, then I have ke = dve = kvi + njve, but now I'm stuck.

Am I doing the right thing?

Thanks.

KK
• May 9th 2009, 12:18 AM
fardeen_gen
Let $k = ad$ and $n = bd$, $gcd(a,b) = 1$.

$ade\equiv 0\pmod{bd}\implies ae\equiv 0\pmod{b}$

Thus $e=\{b, 2b, 3b, ...\; (d-1)b\}$, so such integer exists.

In case $b = 1$, we will not include $e = b$.