Author |
Topic: integers ( mod n): (Read 2105 times) |
|
MonicaMath
Newbie
Gender: 
Posts: 43
|
 |
integers ( mod n):
« on: Sep 6th, 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 7th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print