Printable View
I'm having trouble with a problem, in my abstract algebra class, don't know how to even begin...
Let n be a positive integer. Prove that a and c leave the same remainder when divided by n if and only if a - c = nk for some integer k.
Now, i understand that the division algorithm basically states a = bq + r. In this case, n would be substituted with b. But, I'm a little confused on how to prove what it's asking for, or if I even understand what it's asking for. Please help!
I did get to that point, but see, my problem is, I'm not sure that would acctually prove what I want, because in the begginig, you are assuming what you are trying to prove... theres no way you could find it any other way in the end, cuz in the begginig it was your starting assumtion....Quote:
Originally Posted by topsquark
And I've tried this way, but maybe I'm missing something... but, this is what I got by doing it that way... so far....Quote:
Now you prove it the other way: Assume a - c = nk and show that this gives a = nx + r and c = ny + s means that r = s.
Since a = nx + r and c = ny + s, than filling it in the equation i want to prove, :
nx + r - ny - s = nk
but... I still don't know how to isolate the r and the s.... the other integers don't cancel out, I can simplify it a little bit, but I'm not sure how much help it would be to put it in this form:
r - s = n(y - x + k)
except for the fact that it resembles the first form, (no with integers but with format) I can't see where to go from here.... *sighs* unless i was able to prove that either n = 0 ( which i didn't think it could be, because it says let n be a positive integer) or I have to prove that y - x + k = 0.....
You are right, I goofed. Let's try this for the forward proof:Quote:
Originally Posted by fruitbodywash
Let a - c = nk. We wish to show that both a and c leave the same remainder when divided by n.
So
a = nx + q
c = ny + r
where x, y, q, r are unique positive integers (when.)
Thus
a - c = (nx + q) - (ny + r) = n(x - y) + (q - r)
But
a - c = nk
by hypothesis.
Thus
nk = n(x - y) + (q - r)
Since both q and r are less than n, so is q - r. Thus in order for this equation to be satisfied by integers we must have that k = x - y and 0 = q - r. ie q = r.
Thus
a = nx + r
c = ny + r
and they leave the same remainder.
-Dan
I'm not sure i follow this.... i mean, i understand that q - r will be less than n, but that might not neccisarrily mean that it has to be zero... n could be say... 2 and q - r is 1... and the less than statement would still hold.... I know we want to prove that q - r = 0, but I can't quit seem to understand that step the gets from point A "nk = n(x - y) + (q - r)" to point B "k = (x - y)"... *sighs* thanks for being patient with me :)Quote:
Originally Posted by topsquark
eureka!
ok, i think I got it... let me know if this makes sense...
Known :
a = nx + r
c = ny + s
0 < n
0 <= r < n
0 <= s < n
r - s < n
s - r < n
Ok... now for the rearranging.... using a - c = nk
a - c = nk ==> (nx + r) - (ny + s) = nk
==> nx + r - ny - s = nk ==> r - s = ny - nx + nk
==> r - s = n(y - x + k)
(this next step... is where I'm a little unsure....)
==> (r - s)/n = y - x + k = 0 (because... r - s < n... right?)
==> k = x - y
(back to the first equation) a - c = nk
==> (nx + r) - (ny + s) = n(x - y)
==> nx + r - ny + s = nx - ny
==> r - s = 0 ==> r = s ............? is that right?
( I think that that is what you were trying to say up there, but I'm just re-itterating it to you to make sure that I understand it)
As far as I know that will work. :)Quote:
Originally Posted by fruitbodywash
-Dan
No wonder you are having trouble, you have the home work fromQuote:
Originally Posted by fruitbodywash
the elementary number theory class.
If a and c leave the same remainder when divided by n, then they may beQuote:
Let n be a positive integer. Prove that a and c leave the same remainder when divided by n if and only if a - c = nk for some integer k.
Now, i understand that the division algorithm basically states a = bq + r. In this case, n would be substituted with b. But, I'm a little confused on how to prove what it's asking for, or if I even understand what it's asking for. Please help!
written: a=k1 n + r, c=k2 n + r, so a-c = (k1-k2)n, which proves one half of
the if and only if.
If a-c=k n, then as we have a=k1 n + r1, c=k2 n + r2 for same k1, k2, 0<=r1<n, 0<=r2<n:
a-c = (k1-k2)n + (r1-r2),
so r1-r2= k3 n for some k3, so r1 = k3 n + r2, so a= (k1+k3)n + r2, hence
r1=r2. Which proves the other half of the if and only if.
RonL