Register to reply

2 Questions

by Matthollyw00d
Tags: None
Share this thread:
Matthollyw00d
#1
May31-09, 02:57 PM
P: 92
First Question:
Let Nn be the integer whose decimal expansion consists of n consecutive ones. For example, N2=11 and N7=1,111,111. Show that Nn|Nm iff n|m.

Second Question:
If (a,c)=1, prove that (a,bc)=(a,b).

On the second question I can see that it is true because a and c are relatively prime, I realize that ax1+bx2=1, but I'm having difficulty expressing it in a proof satisfactory way. I think I'm just over looking a fact somewhere in my text.

As for the first one, I'm not very certain as to where at all to start, so any and all help here would be appreciated.

Note that I'm not really wanting the full proof of either, more or less just a few helpful pointers or some key facts that are needed that I'm missing; something to get me started so I can get a better attempt at it.

If anything is unclear, I'll be happy to restate it in a more satisfactory format if possible.

Thanks all.
Thanks all.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
tiny-tim
#2
May31-09, 03:58 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,160
Hi Matthollyw00d!

You're making this far too complicated
Quote Quote by Matthollyw00d View Post
First Question:
Let Nn be the integer whose decimal expansion consists of n consecutive ones. For example, N2=11 and N7=1,111,111. Show that Nn|Nm iff n|m.

Second Question:
If (a,c)=1, prove that (a,bc)=(a,b).
For the first one, just divide what is the remainder?

For the second, write a = np, b = nq, bc = nqc
Matthollyw00d
#3
May31-09, 08:25 PM
P: 92
Would this be sufficient for the first one:

Assume Nn|Nm, then (t)Nn=Nm, t≥1. For all m,n≥1, there exists q,r such that m=qn + r, 0≤r<n.
Next assume m does not divide n, therefore 1≤r<n.
Thus Nm=Nqn+r=10r(s)Nn+Nr
Then, (t)Nn=Nqn+r=10r(s)Nn+Nr
Thus, Nr=Nn(t-s10r)=Nn(d), d≥1, which implies r≥n, which contradicts our hypothesis of r<n.
Thus Nn|Nm iff n|m.

ramsey2879
#4
Jun2-09, 04:07 PM
P: 894
2 Questions

Quote Quote by Matthollyw00d View Post
Would this be sufficient for the first one:

Assume Nn|Nm, then (t)Nn=Nm, t≥1. For all m,n≥1, there exists q,r such that m=qn + r, 0≤r<n.
Next assume m does not divide n, therefore 1≤r<n.
Thus Nm=Nqn+r=10r(s)Nn+Nr
Then, (t)Nn=Nqn+r=10r(s)Nn+Nr
Thus, Nr=Nn(t-s10r)=Nn(d), d≥1, which implies r≥n, which contradicts our hypothesis of r<n.
Thus Nn|Nm iff n|m.
If you work out a couple of divisions as a grade school student is taught a simpler proof should be apparent. First try [tex]/N_6/N_2[/tex] to get 010101. Then Try [tex]N_8/N_4[/tex] to get 00010001. Now what would the result of [tex]N_20/N_5[/tex] be?
Matthollyw00d
#5
Jun2-09, 10:08 PM
P: 92
Quote Quote by ramsey2879 View Post
If you work out a couple of divisions as a grade school student is taught a simpler proof should be apparent. First try [tex]/N_6/N_2[/tex] to get 010101. Then Try [tex]N_8/N_4[/tex] to get 00010001. Now what would the result of [tex]N_2_0/N_5[/tex] be?
00001000010000100001
But I'm not seeing a proof that is simpler than what I did unfortunately. =/
ramsey2879
#6
Jun5-09, 11:06 AM
P: 894
Quote Quote by Matthollyw00d View Post
00001000010000100001
But I'm not seeing a proof that is simpler than what I did unfortunately. =/
Assume 0 < r < n
[tex]m = tn + r[/tex]
[tex]N_{m} = N_{m} - (10^{(t-1)*n + r})*N_{n} \mod N_n[/tex]
[tex]N_{m} = N_{m-n} \mod N_{n}[/tex]
[tex]N_{m} = N_{m-n} - (10^{t-2}*n + r})*N_{n} \mod N_n[/tex]
[tex]0 = N_{m-2n} \mod N_{n}[/tex]
...
[tex]0 = N_{m - tn} \mod N_n[/tex]
[tex]0 = N_{r} \mod N_n[/tex]
[tex] r = 0 [/tex]
Matthollyw00d
#7
Jun5-09, 03:04 PM
P: 92
That would be why I didn't see it, I've yet to learn Modular Arithmetic.
ramsey2879
#8
Jun6-09, 03:45 PM
P: 894
Quote Quote by ramsey2879 View Post
Assume 0 < r < n
[tex]m = tn + r[/tex]
[tex]N_{m} = N_{m} - (10^{(t-1)*n + r})*N_{n} \mod N_n[/tex]
[tex]N_{m} = N_{m-n} \mod N_{n}[/tex]
[tex]N_{m} = N_{m-n} - (10^{t-2}*n + r})*N_{n} \mod N_n[/tex]
[tex]0 = N_{m-2n} \mod N_{n}[/tex]
...
[tex]0 = N_{m - tn} \mod N_n[/tex]
[tex]0 = N_{r} \mod N_n[/tex]
[tex] r = 0 [/tex]
redoing this
[tex]m = tn + r[/tex]
If [tex]N_{n}|N_{m}[/tex] then [tex]N_{n}[/tex] also divides:
[tex]N_{m} - (10^{(t-1)*n + r})*N_{n} [/tex] which has the same remainder i.e., zero But that is [tex] N_{m-n} [/tex] since you just removed the first n [tex]1[/tex]'s. This is simply going through the longhand division process as the divisor multiplied by [tex]10[/tex] to the appropiiate power removes the n most righthand [tex]1[/tex]'s. When doing longhand division in this manner you are not changing the ultimate remainder so we can say that the new term [tex]N_{m-n} = N_{m} \mod N_n[/tex] (i.e. they have the same remainder if divided by [tex]N_n[/tex]).
Likewise we continue the longhand division process by removing the next n most righthand [tex]1[/tex]'s and so on until we removed t*n [tex]1[/tex]'s. The resulting number comprises r [tex]1[/tex]'s and has the same remainder as the original number. So we say [tex]N_{m} = N_{r} \mod N_n[/tex] iff [tex]m = r \mod n[/tex]. Since n|m, r = zero is the only possible r less than n.


Register to reply

Related Discussions
Can u me with this questions ? General Math 2
Questions Advanced Physics Homework 3
Two questions...help please Introductory Physics Homework 4
Three questions. General Physics 3