2 Questions

**Matthollyw00d** · May31-09, 03:57 PM

First Question:
Let N_n be the integer whose decimal expansion consists of n consecutive ones. For example, N₂=11 and N₇=1,111,111. Show that N_n|N_m 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 ax₁+bx₂=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.

**tiny-tim** · May31-09, 04:58 PM

Hi Matthollyw00d!

You're making this far too complicated …

Originally Posted by Matthollyw00d

First Question:
Let N_n be the integer whose decimal expansion consists of n consecutive ones. For example, N₂=11 and N₇=1,111,111. Show that N_n|N_m 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** · May31-09, 09:25 PM

Would this be sufficient for the first one:

Assume N_n|N_m, then (t)N_n=N_m, 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 N_m=N_qn+r=10^r(s)N_n+N_r
Then, (t)N_n=N_qn+r=10^r(s)N_n+N_r
Thus, N_r=N_n(t-s10^r)=N_n(d), d≥1, which implies r≥n, which contradicts our hypothesis of r<n.
Thus N_n|N_m iff n|m.

**ramsey2879** · Jun2-09, 05:07 PM

Originally Posted by Matthollyw00d

Would this be sufficient for the first one:

Assume N_n|N_m, then (t)N_n=N_m, 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 N_m=N_qn+r=10^r(s)N_n+N_r
Then, (t)N_n=N_qn+r=10^r(s)N_n+N_r
Thus, N_r=N_n(t-s10^r)=N_n(d), d≥1, which implies r≥n, which contradicts our hypothesis of r<n.
Thus N_n|N_m 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

to get 010101. Then Try

to get 00010001. Now what would the result of

be?

**Matthollyw00d** · Jun2-09, 11:08 PM

Originally Posted by ramsey2879

If you work out a couple of divisions as a grade school student is taught a simpler proof should be apparent. First try to get 010101. Then Try to get 00010001. Now what would the result of be?

00001000010000100001
But I'm not seeing a proof that is simpler than what I did unfortunately. =/

**ramsey2879** · Jun5-09, 12:06 PM

Originally Posted by Matthollyw00d

00001000010000100001
But I'm not seeing a proof that is simpler than what I did unfortunately. =/

Assume 0 < r < n

$LaTeX Code: N_{m} = N_{m} - (10^{(t-1)*n + r})*N_{n} \\mod N_n$
$LaTeX Code: N_{m} = N_{m-n} \\mod N_{n}$
$LaTeX Code: N_{m} = N_{m-n} - (10^{t-2}*n + r})*N_{n} \\mod N_n$
$LaTeX Code: 0 = N_{m-2n} \\mod N_{n}$
...
$LaTeX Code: 0 = N_{m - tn} \\mod N_n$
$LaTeX Code: 0 = N_{r} \\mod N_n$

**Matthollyw00d** · Jun5-09, 04:04 PM

That would be why I didn't see it, I've yet to learn Modular Arithmetic.

**ramsey2879** · Jun6-09, 04:45 PM

Originally Posted by ramsey2879

Assume 0 < r < n

$LaTeX Code: N_{m} = N_{m} - (10^{(t-1)*n + r})*N_{n} \\mod N_n$
$LaTeX Code: N_{m} = N_{m-n} \\mod N_{n}$
$LaTeX Code: N_{m} = N_{m-n} - (10^{t-2}*n + r})*N_{n} \\mod N_n$
$LaTeX Code: 0 = N_{m-2n} \\mod N_{n}$
...
$LaTeX Code: 0 = N_{m - tn} \\mod N_n$
$LaTeX Code: 0 = N_{r} \\mod N_n$

redoing this

If $LaTeX Code: N_{n}|N_{m}$ then $LaTeX Code: N_{n}$ also divides:
$LaTeX Code: N_{m} - (10^{(t-1)*n + r})*N_{n}$ which has the same remainder i.e., zero But that is $LaTeX Code: N_{m-n}$ since you just removed the first n

's. This is simply going through the longhand division process as the divisor multiplied by

to the appropiiate power removes the n most righthand

's. When doing longhand division in this manner you are not changing the ultimate remainder so we can say that the new term $LaTeX Code: N_{m-n} = N_{m} \\mod N_n$ (i.e. they have the same remainder if divided by

).
Likewise we continue the longhand division process by removing the next n most righthand

's and so on until we removed t*n

's. The resulting number comprises r

's and has the same remainder as the original number. So we say $LaTeX Code: N_{m} = N_{r} \\mod N_n$ iff $LaTeX Code: m = r \\mod n$ . Since n|m, r = zero is the only possible r less than n.