Mixing
Uniqueness of fractional parts of integer multiples of a fraction
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
By considering lines on a torus, I had the following observation.
Let $a/b$ be a non-zero irreducible fraction with $|a| > |b|$. Then the fractional part of the integer multiples
$$
kfracab qquad k in big1, 2, ldots, (b-1)big
$$
are unique and are
$$
frac1b,enspace frac2b,enspace ldots,enspace fracb-1b.
$$
It feels fairly simple to prove and is easy with explicit examples, but I can't seem to prove it in general (supposing that it is true in general, that is).
Attempt
Consider two multiples, say $ma/b$ and $na/b$ for $m neq n$. Suppose that they have the same fractional part, say $r$. This means that there are integers $p, q$ such that
$$
ma = pb + r qquadtextandqquad na = qb + r
$$
so by rearranging we have
$$
a(m - n) = b(p - q)
$$
and
$$
fracab = fracp - qm - n
$$
since $m neq n$.
This is all that I could determine so far, and I'm not sure how to derive a contradiction from this. I would want to use the fact that $a$ and $b$ are coprime somehow (since $a/b$ is irreducible), but I couldn't figure anything else out. Hints would be more valuable than a solution for now.
algebra-precalculus
asked Jul 24 at 14:45
Bill Wallis
1,7811821
add a comment |Â
up vote
2
down vote
favorite
By considering lines on a torus, I had the following observation.
Let $a/b$ be a non-zero irreducible fraction with $|a| > |b|$. Then the fractional part of the integer multiples
$$
kfracab qquad k in big1, 2, ldots, (b-1)big
$$
are unique and are
$$
frac1b,enspace frac2b,enspace ldots,enspace fracb-1b.
$$
It feels fairly simple to prove and is easy with explicit examples, but I can't seem to prove it in general (supposing that it is true in general, that is).
Attempt
Consider two multiples, say $ma/b$ and $na/b$ for $m neq n$. Suppose that they have the same fractional part, say $r$. This means that there are integers $p, q$ such that
$$
ma = pb + r qquadtextandqquad na = qb + r
$$
so by rearranging we have
$$
a(m - n) = b(p - q)
$$
and
$$
fracab = fracp - qm - n
$$
since $m neq n$.
This is all that I could determine so far, and I'm not sure how to derive a contradiction from this. I would want to use the fact that $a$ and $b$ are coprime somehow (since $a/b$ is irreducible), but I couldn't figure anything else out. Hints would be more valuable than a solution for now.
algebra-precalculus
asked Jul 24 at 14:45
Bill Wallis
1,7811821
1
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
By considering lines on a torus, I had the following observation.
Let $a/b$ be a non-zero irreducible fraction with $|a| > |b|$. Then the fractional part of the integer multiples
$$
kfracab qquad k in big1, 2, ldots, (b-1)big
$$
are unique and are
$$
frac1b,enspace frac2b,enspace ldots,enspace fracb-1b.
$$
It feels fairly simple to prove and is easy with explicit examples, but I can't seem to prove it in general (supposing that it is true in general, that is).
Attempt
Consider two multiples, say $ma/b$ and $na/b$ for $m neq n$. Suppose that they have the same fractional part, say $r$. This means that there are integers $p, q$ such that
$$
ma = pb + r qquadtextandqquad na = qb + r
$$
so by rearranging we have
$$
a(m - n) = b(p - q)
$$
and
$$
fracab = fracp - qm - n
$$
since $m neq n$.
This is all that I could determine so far, and I'm not sure how to derive a contradiction from this. I would want to use the fact that $a$ and $b$ are coprime somehow (since $a/b$ is irreducible), but I couldn't figure anything else out. Hints would be more valuable than a solution for now.
algebra-precalculus
asked Jul 24 at 14:45
Bill Wallis
1,7811821
By considering lines on a torus, I had the following observation.
Let $a/b$ be a non-zero irreducible fraction with $|a| > |b|$. Then the fractional part of the integer multiples
$$
kfracab qquad k in big1, 2, ldots, (b-1)big
$$
are unique and are
$$
frac1b,enspace frac2b,enspace ldots,enspace fracb-1b.
$$
It feels fairly simple to prove and is easy with explicit examples, but I can't seem to prove it in general (supposing that it is true in general, that is).
Attempt
Consider two multiples, say $ma/b$ and $na/b$ for $m neq n$. Suppose that they have the same fractional part, say $r$. This means that there are integers $p, q$ such that
$$
ma = pb + r qquadtextandqquad na = qb + r
$$
so by rearranging we have
$$
a(m - n) = b(p - q)
$$
and
$$
fracab = fracp - qm - n
$$
since $m neq n$.
This is all that I could determine so far, and I'm not sure how to derive a contradiction from this. I would want to use the fact that $a$ and $b$ are coprime somehow (since $a/b$ is irreducible), but I couldn't figure anything else out. Hints would be more valuable than a solution for now.
algebra-precalculus
asked Jul 24 at 14:45
Bill Wallis
1,7811821
edited Jul 25 at 20:32
asked Jul 24 at 14:45
Bill Wallis
1,7811821
asked Jul 24 at 14:45
Bill Wallis
1,7811821
asked Jul 24 at 14:45
Bill Wallis
1,7811821
1,7811821
1
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00
add a comment |Â
1
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00
1
1
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Well, I congratulate you. You've rediscovered a very important fact. The important point is that if $a$ and $b$ are relatively prime, then there is a $c$ such that $acequiv1pmodb$. Do you see how this solves your problem?
As for how we know there is such a $c$ I suggest you read about the extended Euclidean algorithm. If the Wikipedia post is too terse, you can google "extended Euclidean algorithm" to find lots of examples. You may want to google "Euclidean algorithm" first.
answered Jul 24 at 15:07
saulspatz
10.4k21323
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Well, I congratulate you. You've rediscovered a very important fact. The important point is that if $a$ and $b$ are relatively prime, then there is a $c$ such that $acequiv1pmodb$. Do you see how this solves your problem?
As for how we know there is such a $c$ I suggest you read about the extended Euclidean algorithm. If the Wikipedia post is too terse, you can google "extended Euclidean algorithm" to find lots of examples. You may want to google "Euclidean algorithm" first.
answered Jul 24 at 15:07
saulspatz
10.4k21323
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
add a comment |Â
up vote
2
down vote
accepted
Well, I congratulate you. You've rediscovered a very important fact. The important point is that if $a$ and $b$ are relatively prime, then there is a $c$ such that $acequiv1pmodb$. Do you see how this solves your problem?
As for how we know there is such a $c$ I suggest you read about the extended Euclidean algorithm. If the Wikipedia post is too terse, you can google "extended Euclidean algorithm" to find lots of examples. You may want to google "Euclidean algorithm" first.
answered Jul 24 at 15:07
saulspatz
10.4k21323
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Well, I congratulate you. You've rediscovered a very important fact. The important point is that if $a$ and $b$ are relatively prime, then there is a $c$ such that $acequiv1pmodb$. Do you see how this solves your problem?
As for how we know there is such a $c$ I suggest you read about the extended Euclidean algorithm. If the Wikipedia post is too terse, you can google "extended Euclidean algorithm" to find lots of examples. You may want to google "Euclidean algorithm" first.
answered Jul 24 at 15:07
saulspatz
10.4k21323
Well, I congratulate you. You've rediscovered a very important fact. The important point is that if $a$ and $b$ are relatively prime, then there is a $c$ such that $acequiv1pmodb$. Do you see how this solves your problem?
As for how we know there is such a $c$ I suggest you read about the extended Euclidean algorithm. If the Wikipedia post is too terse, you can google "extended Euclidean algorithm" to find lots of examples. You may want to google "Euclidean algorithm" first.
answered Jul 24 at 15:07
saulspatz
10.4k21323
answered Jul 24 at 15:07
saulspatz
10.4k21323
answered Jul 24 at 15:07
saulspatz
10.4k21323
answered Jul 24 at 15:07
saulspatz
10.4k21323
10.4k21323
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
add a comment |Â
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
Ah yes, I remember reading that if $a$ and $b$ are coprime there are integers $c$ and $d$ such that $ac + bd = 1$. I'm struggling to use this fact though --- particularly since I cannot get a $1$ to appear with manipulations of $ma equiv na pmodb$, or anything else that would cause a contradiction.
– Bill Wallis
Jul 24 at 15:41
1
1
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Well, if $ac+bd=1$ then $acequiv1pmodb,$ correct? Then multiply both sides of $naequivmapmodb$ by $c$.
– saulspatz
Jul 24 at 15:42
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
Oh, and this gives that $m equiv n pmodb$! That makes a lot of sense, thank you.
– Bill Wallis
Jul 24 at 15:46
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861426%2funiqueness-of-fractional-parts-of-integer-multiples-of-a-fraction%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
You have $maequiv napmodb$ where $a$ and $b$ are relatively prime. Have you studied this yet?
– saulspatz
Jul 24 at 14:52
@saulspatz Not yet, my elementary Number Theory teaching was super limited so we never got onto modular congruences with coprime numbers.
– Bill Wallis
Jul 24 at 15:00