Mixing
Let $R_n = underbrace11ldots1_n$. Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $R_n = underbrace11ldots1_n$.
1) Prove that if $n mid m$, then $R_n mid R_m$.
2) Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.
I have solved only the first task:
$$m = nk Rightarrow R_m = underbrace11ldots1_nk\
R_m = R_n cdot underbrace1underbrace00ldots0_n-11underbrace00ldots0_n-11 ldots 1underbrace00ldots0_n-11_k mbox of 1$$
Using the sum of geometric progressions, we can write that $R_n = frac10^n-19$. But I don't know how to continue the second task. Can you help me solve it? Thanks!
divisibility greatest-common-divisor geometric-progressions
asked Jul 29 at 17:53
Iulian Oleniuc
3619
add a comment |Â
up vote
2
down vote
favorite
Let $R_n = underbrace11ldots1_n$.
1) Prove that if $n mid m$, then $R_n mid R_m$.
2) Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.
I have solved only the first task:
$$m = nk Rightarrow R_m = underbrace11ldots1_nk\
R_m = R_n cdot underbrace1underbrace00ldots0_n-11underbrace00ldots0_n-11 ldots 1underbrace00ldots0_n-11_k mbox of 1$$
Using the sum of geometric progressions, we can write that $R_n = frac10^n-19$. But I don't know how to continue the second task. Can you help me solve it? Thanks!
divisibility greatest-common-divisor geometric-progressions
asked Jul 29 at 17:53
Iulian Oleniuc
3619
2
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $R_n = underbrace11ldots1_n$.
1) Prove that if $n mid m$, then $R_n mid R_m$.
2) Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.
I have solved only the first task:
$$m = nk Rightarrow R_m = underbrace11ldots1_nk\
R_m = R_n cdot underbrace1underbrace00ldots0_n-11underbrace00ldots0_n-11 ldots 1underbrace00ldots0_n-11_k mbox of 1$$
Using the sum of geometric progressions, we can write that $R_n = frac10^n-19$. But I don't know how to continue the second task. Can you help me solve it? Thanks!
divisibility greatest-common-divisor geometric-progressions
asked Jul 29 at 17:53
Iulian Oleniuc
3619
Let $R_n = underbrace11ldots1_n$.
1) Prove that if $n mid m$, then $R_n mid R_m$.
2) Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.
I have solved only the first task:
$$m = nk Rightarrow R_m = underbrace11ldots1_nk\
R_m = R_n cdot underbrace1underbrace00ldots0_n-11underbrace00ldots0_n-11 ldots 1underbrace00ldots0_n-11_k mbox of 1$$
Using the sum of geometric progressions, we can write that $R_n = frac10^n-19$. But I don't know how to continue the second task. Can you help me solve it? Thanks!
divisibility greatest-common-divisor geometric-progressions
asked Jul 29 at 17:53
Iulian Oleniuc
3619
edited Jul 29 at 22:56
asked Jul 29 at 17:53
Iulian Oleniuc
3619
asked Jul 29 at 17:53
Iulian Oleniuc
3619
asked Jul 29 at 17:53
Iulian Oleniuc
3619
3619
2
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56
add a comment |Â
2
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56
2
2
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
1) Write $m=nk$ then $$10^m-1 =10^nk-1 = (10^n-1)Big((10^n)^k-1+...+10^n+1Big)$$
so $$10^n-1mid 10^m-1implies R_nmid R_m$$
Hint for 2):
Use the fact that $$gcd(a^n-1,a^m-1)= a^gcd (m,n)-1$$
answered Jul 29 at 17:56
greedoid
26.1k93473
add a comment |Â
up vote
1
down vote
Let $dmid m$ and $dmid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=frac10^dj-19=fracleft(10^dright)^j-1^j9=frac10^d-19cdotsum_i=0^j-1left(10^dright)^i=R_dcdotsum_i=0^j-1left(10^dright)^i,$$ so that $R_dmid R_m,$ and likewise, $R_dmid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=gcd(m,n).$ On the other hand, we can show that if $dmid R_m$ and $dmid R_n,$ then $dmid R_gcd(m,n),$ so that $$R_gcd(m,n)=gcdleft(R_m,R_nright).$$ What can we then conclude?
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
add a comment |Â
up vote
1
down vote
Let $gcd(R_n, R_m) = d$.
So $gcd(R_n,R_m) = gcd(frac10^n-19, frac 10^m-19) =frac 19gcd(10^n-1, 10^m - 1)$
and
$gcd(10^n-1, 10^m - 1)=gcd(10^n-1, (10^m-1)-(10^n-1)) $
$= gcd(10^n-1, 10^m - 10^n) = $
$gcd(10^n-1, 10^min(n,m)(10^max(n,m)-min(n,m) -1))$
which, as $gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $gcd(10^n-1, 10^v- 1)$ where $v=max(n,m)-min(n,m)$.
And that's it, really...
By induction we can replicate Euclid's algorithm to get $k*n + j*m = gcd(n,m)$ to show that $gcd(10^n-1, 10^m-1) = 10^gcd(n,m)-1$ and as $gcd(n,m) = 1$ then $gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.
And $gcd(R_n,R_m) = $
$gcd(frac10^n-19, frac 10^m-19) = $
$frac 19gcd(10^n-1, 10^m - 1)= 1$.
answered Jul 29 at 18:13
fleablood
60.2k22575
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
1) Write $m=nk$ then $$10^m-1 =10^nk-1 = (10^n-1)Big((10^n)^k-1+...+10^n+1Big)$$
so $$10^n-1mid 10^m-1implies R_nmid R_m$$
Hint for 2):
Use the fact that $$gcd(a^n-1,a^m-1)= a^gcd (m,n)-1$$
answered Jul 29 at 17:56
greedoid
26.1k93473
add a comment |Â
up vote
2
down vote
accepted
1) Write $m=nk$ then $$10^m-1 =10^nk-1 = (10^n-1)Big((10^n)^k-1+...+10^n+1Big)$$
so $$10^n-1mid 10^m-1implies R_nmid R_m$$
Hint for 2):
Use the fact that $$gcd(a^n-1,a^m-1)= a^gcd (m,n)-1$$
answered Jul 29 at 17:56
greedoid
26.1k93473
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
1) Write $m=nk$ then $$10^m-1 =10^nk-1 = (10^n-1)Big((10^n)^k-1+...+10^n+1Big)$$
so $$10^n-1mid 10^m-1implies R_nmid R_m$$
Hint for 2):
Use the fact that $$gcd(a^n-1,a^m-1)= a^gcd (m,n)-1$$
answered Jul 29 at 17:56
greedoid
26.1k93473
1) Write $m=nk$ then $$10^m-1 =10^nk-1 = (10^n-1)Big((10^n)^k-1+...+10^n+1Big)$$
so $$10^n-1mid 10^m-1implies R_nmid R_m$$
Hint for 2):
Use the fact that $$gcd(a^n-1,a^m-1)= a^gcd (m,n)-1$$
answered Jul 29 at 17:56
greedoid
26.1k93473
answered Jul 29 at 17:56
greedoid
26.1k93473
answered Jul 29 at 17:56
greedoid
26.1k93473
answered Jul 29 at 17:56
greedoid
26.1k93473
26.1k93473
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $dmid m$ and $dmid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=frac10^dj-19=fracleft(10^dright)^j-1^j9=frac10^d-19cdotsum_i=0^j-1left(10^dright)^i=R_dcdotsum_i=0^j-1left(10^dright)^i,$$ so that $R_dmid R_m,$ and likewise, $R_dmid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=gcd(m,n).$ On the other hand, we can show that if $dmid R_m$ and $dmid R_n,$ then $dmid R_gcd(m,n),$ so that $$R_gcd(m,n)=gcdleft(R_m,R_nright).$$ What can we then conclude?
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
add a comment |Â
up vote
1
down vote
Let $dmid m$ and $dmid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=frac10^dj-19=fracleft(10^dright)^j-1^j9=frac10^d-19cdotsum_i=0^j-1left(10^dright)^i=R_dcdotsum_i=0^j-1left(10^dright)^i,$$ so that $R_dmid R_m,$ and likewise, $R_dmid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=gcd(m,n).$ On the other hand, we can show that if $dmid R_m$ and $dmid R_n,$ then $dmid R_gcd(m,n),$ so that $$R_gcd(m,n)=gcdleft(R_m,R_nright).$$ What can we then conclude?
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $dmid m$ and $dmid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=frac10^dj-19=fracleft(10^dright)^j-1^j9=frac10^d-19cdotsum_i=0^j-1left(10^dright)^i=R_dcdotsum_i=0^j-1left(10^dright)^i,$$ so that $R_dmid R_m,$ and likewise, $R_dmid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=gcd(m,n).$ On the other hand, we can show that if $dmid R_m$ and $dmid R_n,$ then $dmid R_gcd(m,n),$ so that $$R_gcd(m,n)=gcdleft(R_m,R_nright).$$ What can we then conclude?
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
Let $dmid m$ and $dmid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=frac10^dj-19=fracleft(10^dright)^j-1^j9=frac10^d-19cdotsum_i=0^j-1left(10^dright)^i=R_dcdotsum_i=0^j-1left(10^dright)^i,$$ so that $R_dmid R_m,$ and likewise, $R_dmid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=gcd(m,n).$ On the other hand, we can show that if $dmid R_m$ and $dmid R_n,$ then $dmid R_gcd(m,n),$ so that $$R_gcd(m,n)=gcdleft(R_m,R_nright).$$ What can we then conclude?
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
answered Jul 29 at 18:04
Cameron Buie
83.5k771152
83.5k771152
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $gcd(R_n, R_m) = d$.
So $gcd(R_n,R_m) = gcd(frac10^n-19, frac 10^m-19) =frac 19gcd(10^n-1, 10^m - 1)$
and
$gcd(10^n-1, 10^m - 1)=gcd(10^n-1, (10^m-1)-(10^n-1)) $
$= gcd(10^n-1, 10^m - 10^n) = $
$gcd(10^n-1, 10^min(n,m)(10^max(n,m)-min(n,m) -1))$
which, as $gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $gcd(10^n-1, 10^v- 1)$ where $v=max(n,m)-min(n,m)$.
And that's it, really...
By induction we can replicate Euclid's algorithm to get $k*n + j*m = gcd(n,m)$ to show that $gcd(10^n-1, 10^m-1) = 10^gcd(n,m)-1$ and as $gcd(n,m) = 1$ then $gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.
And $gcd(R_n,R_m) = $
$gcd(frac10^n-19, frac 10^m-19) = $
$frac 19gcd(10^n-1, 10^m - 1)= 1$.
answered Jul 29 at 18:13
fleablood
60.2k22575
add a comment |Â
up vote
1
down vote
Let $gcd(R_n, R_m) = d$.
So $gcd(R_n,R_m) = gcd(frac10^n-19, frac 10^m-19) =frac 19gcd(10^n-1, 10^m - 1)$
and
$gcd(10^n-1, 10^m - 1)=gcd(10^n-1, (10^m-1)-(10^n-1)) $
$= gcd(10^n-1, 10^m - 10^n) = $
$gcd(10^n-1, 10^min(n,m)(10^max(n,m)-min(n,m) -1))$
which, as $gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $gcd(10^n-1, 10^v- 1)$ where $v=max(n,m)-min(n,m)$.
And that's it, really...
By induction we can replicate Euclid's algorithm to get $k*n + j*m = gcd(n,m)$ to show that $gcd(10^n-1, 10^m-1) = 10^gcd(n,m)-1$ and as $gcd(n,m) = 1$ then $gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.
And $gcd(R_n,R_m) = $
$gcd(frac10^n-19, frac 10^m-19) = $
$frac 19gcd(10^n-1, 10^m - 1)= 1$.
answered Jul 29 at 18:13
fleablood
60.2k22575
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $gcd(R_n, R_m) = d$.
So $gcd(R_n,R_m) = gcd(frac10^n-19, frac 10^m-19) =frac 19gcd(10^n-1, 10^m - 1)$
and
$gcd(10^n-1, 10^m - 1)=gcd(10^n-1, (10^m-1)-(10^n-1)) $
$= gcd(10^n-1, 10^m - 10^n) = $
$gcd(10^n-1, 10^min(n,m)(10^max(n,m)-min(n,m) -1))$
which, as $gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $gcd(10^n-1, 10^v- 1)$ where $v=max(n,m)-min(n,m)$.
And that's it, really...
By induction we can replicate Euclid's algorithm to get $k*n + j*m = gcd(n,m)$ to show that $gcd(10^n-1, 10^m-1) = 10^gcd(n,m)-1$ and as $gcd(n,m) = 1$ then $gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.
And $gcd(R_n,R_m) = $
$gcd(frac10^n-19, frac 10^m-19) = $
$frac 19gcd(10^n-1, 10^m - 1)= 1$.
answered Jul 29 at 18:13
fleablood
60.2k22575
Let $gcd(R_n, R_m) = d$.
So $gcd(R_n,R_m) = gcd(frac10^n-19, frac 10^m-19) =frac 19gcd(10^n-1, 10^m - 1)$
and
$gcd(10^n-1, 10^m - 1)=gcd(10^n-1, (10^m-1)-(10^n-1)) $
$= gcd(10^n-1, 10^m - 10^n) = $
$gcd(10^n-1, 10^min(n,m)(10^max(n,m)-min(n,m) -1))$
which, as $gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $gcd(10^n-1, 10^v- 1)$ where $v=max(n,m)-min(n,m)$.
And that's it, really...
By induction we can replicate Euclid's algorithm to get $k*n + j*m = gcd(n,m)$ to show that $gcd(10^n-1, 10^m-1) = 10^gcd(n,m)-1$ and as $gcd(n,m) = 1$ then $gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.
And $gcd(R_n,R_m) = $
$gcd(frac10^n-19, frac 10^m-19) = $
$frac 19gcd(10^n-1, 10^m - 1)= 1$.
answered Jul 29 at 18:13
fleablood
60.2k22575
answered Jul 29 at 18:13
fleablood
60.2k22575
answered Jul 29 at 18:13
fleablood
60.2k22575
answered Jul 29 at 18:13
fleablood
60.2k22575
60.2k22575
add a comment |Â
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%2f2866263%2flet-r-n-underbrace11-ldots1-n-prove-that-if-n-m-1-then-r-n%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
2
Prove that for $n>m$, $gcd(R_m,R_n)=gcd(R_m,R_n-m)$.
– Lord Shark the Unknown
Jul 29 at 17:56