Author 
Topic: integers ( mod n): (Read 2104 times) 

MonicaMath
Newbie
Gender:
Posts: 43


integers ( mod n):
« on: Sep 6^{th}, 2009, 4:42pm » 
Quote Modify

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: integers ( mod n):
« Reply #1 on: Sep 7^{th}, 2009, 1:05am » 
Quote Modify

for 1, use the fact that m and n have a common factor. You can take k=n/gcd(m,n), then mk is m/gcd(m,n)*n = 0 (mod n) For 2, assume that there is such an y, then show that it contradicts that gcd(m,n) > 1 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



