wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> wanted >> integers ( mod n):
        
(Message started by: MonicaMath on Sep 6^th, 2009, 4:42pm)

Title: integers ( mod n):
Post by MonicaMath on Sep 6^th, 2009, 4:42pm

Hi

I have this question to solve, please if you know something can help post it...

" If m, n are integers with m<=n, and n>1. If gcd(m,n)>1,
(1) show that there exists an integer 1<=k <n such that: mk=0(mod n)
{it means that there is integer q with mk=nq}

and (2) show that there is no integer y with my=1 (mod n)

Thanks in advance for help

Title: Re: integers ( mod n):
Post by towr on Sep 7^th, 2009, 1:05am

for 1, use the fact that m and n have a common factor.
[hide]You can take k=n/gcd(m,n), then mk is m/gcd(m,n)*n = 0 (mod n)[/hide]

For 2, assume that there is such an y, then show that it contradicts that gcd(m,n) > 1
[hide]m y = 1 + q n
gcd(m,n) divides the left side, so it must divide the right side.
gcd(m,n) divides q n, so it must also divide 1 to divide (1 + q n)
But that means it is 1, which contradicts that it is greater than 1.
[/hide]