Results 1 to 2 of 2

Math Help - Congruence problem with gcd

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One Congruence Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 29th 2010, 10:51 PM
  2. A congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 19th 2010, 07:47 PM
  3. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 11:24 AM
  4. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 9th 2009, 03:14 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum