Thread: 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

Let and , .



Thus , so such integer exists.

In case , we will not include .