Mixing
Recurring Decimal Expansion
For any natural number $n>1$, we write the infinite decimal expansion of $frac 1n$ (for example, $frac 14$ is written as $0.24999$... instead of $0.25$). We need to determine the length of the non-periodic part of the infinite decimal expansion of $frac 1n$.
I tried many methods, a somewhat promising one was to assume $frac 1n$ to be some $0.abbbbb$..., where ‘$a$’ denotes the non-recurring part which has $r$ digits including zero, while ‘$b$’ is the recurring part. But I get stuck at deciding the lower and upper bounds for $r$. Please help.
(Please note: this is my first post on this website. So if I have to improve the way I should post the question in, please let me know how to correct the errors in my post. Thanks.)
number-theory elementary-number-theory rational-numbers
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
|
show 1 more comment
For any natural number $n>1$, we write the infinite decimal expansion of $frac 1n$ (for example, $frac 14$ is written as $0.24999$... instead of $0.25$). We need to determine the length of the non-periodic part of the infinite decimal expansion of $frac 1n$.
I tried many methods, a somewhat promising one was to assume $frac 1n$ to be some $0.abbbbb$..., where ‘$a$’ denotes the non-recurring part which has $r$ digits including zero, while ‘$b$’ is the recurring part. But I get stuck at deciding the lower and upper bounds for $r$. Please help.
(Please note: this is my first post on this website. So if I have to improve the way I should post the question in, please let me know how to correct the errors in my post. Thanks.)
number-theory elementary-number-theory rational-numbers
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
4
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
1
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
1
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
1
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
2
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01
|
show 1 more comment
For any natural number $n>1$, we write the infinite decimal expansion of $frac 1n$ (for example, $frac 14$ is written as $0.24999$... instead of $0.25$). We need to determine the length of the non-periodic part of the infinite decimal expansion of $frac 1n$.
I tried many methods, a somewhat promising one was to assume $frac 1n$ to be some $0.abbbbb$..., where ‘$a$’ denotes the non-recurring part which has $r$ digits including zero, while ‘$b$’ is the recurring part. But I get stuck at deciding the lower and upper bounds for $r$. Please help.
(Please note: this is my first post on this website. So if I have to improve the way I should post the question in, please let me know how to correct the errors in my post. Thanks.)
number-theory elementary-number-theory rational-numbers
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
For any natural number $n>1$, we write the infinite decimal expansion of $frac 1n$ (for example, $frac 14$ is written as $0.24999$... instead of $0.25$). We need to determine the length of the non-periodic part of the infinite decimal expansion of $frac 1n$.
I tried many methods, a somewhat promising one was to assume $frac 1n$ to be some $0.abbbbb$..., where ‘$a$’ denotes the non-recurring part which has $r$ digits including zero, while ‘$b$’ is the recurring part. But I get stuck at deciding the lower and upper bounds for $r$. Please help.
(Please note: this is my first post on this website. So if I have to improve the way I should post the question in, please let me know how to correct the errors in my post. Thanks.)
number-theory elementary-number-theory rational-numbers
number-theory elementary-number-theory rational-numbers
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
edited Jan 3 at 19:09
Anu Radha
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
asked Dec 31 '18 at 18:27
Anu RadhaAnu Radha
1359
1359
4
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
1
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
1
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
1
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
2
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01
|
show 1 more comment
4
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
1
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
1
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
1
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
2
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01
4
4
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
1
1
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
1
1
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
1
1
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
2
2
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01
|
show 1 more comment
1 Answer
1
active
oldest
votes
Lemma:
For every number $nin N$ that is not divisible by 2 and 5, there exists $kin N$ such that $nmid10^k-1$
Proof: Suppose that the statement is not true, i.e. $10^k-1notequiv0 pmod n$ for all values of $k$. There are infinitely many values of $k$ and just $n-1$ possible values ($1dots n-1$) for $10^k-1pmod n$. So by pidgeon hole principle there are two different values $k_1, k_2$ such that:
$$10^{k_1}-1equiv10^{k_2}-1pmod n,quad (k_1>k_2)$$
This simply means that:
$$10^{k_1}-10^{k_2}equiv0pmod n$$
$$10^{k_2}(10^{k1-k2}-1)equiv0pmod n$$
Number $n$ has no factors 2 and 5 so obviously $nnmid 10^{k_2}$ which implies that $nmid(10^{k_1-k_2}-1)$ or:
$$nmid10^k-1$$
...where $k=k_1-k_2$.
End of lemma proof.
Part 1:
Let us now show that:
For every number $n$ such that $2nmid n$ and $5nmid n$, decimal representation of $1/n$ has no pre-periodic part. In other words, $1/n$ can be written as: $$frac 1n=0.aaadots=0.bar{a}tag{1}$$
...where $a$ stands for a group of repeating digits (possibly starting with zero) of length $l_a$. For example for $n=7$: $1/7=0.overline{142857}$, so $a=142857$ and $l_a=6$.
One can easily show that (1) can be rewritten in the following way:
$${frac1n}=frac{a}{10^{l_a}-1}$$
$$a=frac{10^{l_a}-1}{n}$$
According to our lemma, it's guaranted that there exists $l_a$ such that $nmid 10^{l_a}-1$ so it's is possible to find $a$ for every $n$ such that $1/n=0.bar{a}$, without a pre-periodic part.
Part 2
If $2mid n$ or $5mid n$, decimal representation of $1/n$ has a pre-periodic part:
$$frac1n=0.boverline {a}tag{2}$$
...with the lenght of pre-periodic group of digits $b$ equal to $l_b$ and length of periodic group of digits $a$ equal to $l_a$.
Suppose the pposite, that there is some number $n$ divisible by either 2 or 5 such that:
$$frac1n=0.bar{a}=frac{a}{10^{l_a}-1}$$
$$na=10^{l_a}-1$$
...which is impossible because the LHS is divisible by 2 or 5 and the RHS is clearly not.
Based on part 1 and 2 we now know that:
Decimal representation of $1/n$ has pre-periodic part if and only if $2mid n$ or $5mid n$.
Part 3
For a number $n$ of the form $n=2^p5^qm$ and $2,5nmid m$ the length of pre-periodic part is exactly $max(p,q)$.
It can be easily proved that any number of the form $0.bbar{a}$ can be written as:
$$0.bbar{a}=frac{b}{10^{l_b}}+frac{a}{10^{l_b}(10^{l_a}-1)}tag{3}$$
Because $m$ is not divisible by 2 or 5, we can write $1/m$ as:
$$frac1m=frac{a}{10^{l_a}-1}$$
which means that:
$$frac1n=frac1{2^p5^q} cdot frac1m$$
If we introduce:
$$r=max(p,q)$$
we get:
$$frac1n=frac{2^{r-p}5^{r-q}}{10^r} cdot frac1m=frac{2^{r-p}5^{r-q}a}{10^r(10^{l_a}-1)}tag{4}$$
Now look at (4) carefully.
Case 1:
$$2^{r-p}5^{r-q}a<10^{l_a}-1$$
By comparing (3) and (4), the length of pre-periodic part is $r$, and the pre-periodic part is made of zeroes $b=0$. Periodic part is equal to $2^{r-p}5^{r-q}a$ and the length of the periodic part is $l_a$.
Case 2:
$$2^{r-p}5^{r-q}a>10^{l_a}-1$$
In that case you can write:
$$2^{r-p}5^{r-q}a=s(10^{l_a}-1)+a_1$$
...and (4) becomes:
$$frac1n=frac{s(10^{l_a}-1)+a_1}{10^r(10^{l_a}-1)}=frac{s}{10^r}+frac{a_1}{10^r(10^{l_a}-1)}$$
By comparing the last expression with (4), the length of the pre-periodic part $s$ is again $r$ and the length of repeating sequence $a_1$ is again $l_a$.
Conclusion
- The length of the periodic part in the decimal representation of $1/n$ is determined by the length of periodic part in $1/m$ with $m$ being the greatest divisor of $n$ such that $2nmid m$ and $5nmid m$.
- Pre-periodic part exists only if $n$ is of the form $2^p5^qm$.
- The length of the pre-periodic part is $max(p,q)$
Interesting example
$$frac{1}{19}=0.overline{052631578947368421}$$
Periodic part has 18 digits. Now take a look at:
$$frac{1}{760}=frac{1}{2^3cdot5cdot19}=0.001overline{315789473684210526}$$
Pre-periodic part has length 3 (because the biggest power of 2 or 5 in $n=760$ is 3). And the periodic part has length 18, same length as in $1/19$.
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057935%2frecurring-decimal-expansion%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Lemma:
For every number $nin N$ that is not divisible by 2 and 5, there exists $kin N$ such that $nmid10^k-1$
Proof: Suppose that the statement is not true, i.e. $10^k-1notequiv0 pmod n$ for all values of $k$. There are infinitely many values of $k$ and just $n-1$ possible values ($1dots n-1$) for $10^k-1pmod n$. So by pidgeon hole principle there are two different values $k_1, k_2$ such that:
$$10^{k_1}-1equiv10^{k_2}-1pmod n,quad (k_1>k_2)$$
This simply means that:
$$10^{k_1}-10^{k_2}equiv0pmod n$$
$$10^{k_2}(10^{k1-k2}-1)equiv0pmod n$$
Number $n$ has no factors 2 and 5 so obviously $nnmid 10^{k_2}$ which implies that $nmid(10^{k_1-k_2}-1)$ or:
$$nmid10^k-1$$
...where $k=k_1-k_2$.
End of lemma proof.
Part 1:
Let us now show that:
For every number $n$ such that $2nmid n$ and $5nmid n$, decimal representation of $1/n$ has no pre-periodic part. In other words, $1/n$ can be written as: $$frac 1n=0.aaadots=0.bar{a}tag{1}$$
...where $a$ stands for a group of repeating digits (possibly starting with zero) of length $l_a$. For example for $n=7$: $1/7=0.overline{142857}$, so $a=142857$ and $l_a=6$.
One can easily show that (1) can be rewritten in the following way:
$${frac1n}=frac{a}{10^{l_a}-1}$$
$$a=frac{10^{l_a}-1}{n}$$
According to our lemma, it's guaranted that there exists $l_a$ such that $nmid 10^{l_a}-1$ so it's is possible to find $a$ for every $n$ such that $1/n=0.bar{a}$, without a pre-periodic part.
Part 2
If $2mid n$ or $5mid n$, decimal representation of $1/n$ has a pre-periodic part:
$$frac1n=0.boverline {a}tag{2}$$
...with the lenght of pre-periodic group of digits $b$ equal to $l_b$ and length of periodic group of digits $a$ equal to $l_a$.
Suppose the pposite, that there is some number $n$ divisible by either 2 or 5 such that:
$$frac1n=0.bar{a}=frac{a}{10^{l_a}-1}$$
$$na=10^{l_a}-1$$
...which is impossible because the LHS is divisible by 2 or 5 and the RHS is clearly not.
Based on part 1 and 2 we now know that:
Decimal representation of $1/n$ has pre-periodic part if and only if $2mid n$ or $5mid n$.
Part 3
For a number $n$ of the form $n=2^p5^qm$ and $2,5nmid m$ the length of pre-periodic part is exactly $max(p,q)$.
It can be easily proved that any number of the form $0.bbar{a}$ can be written as:
$$0.bbar{a}=frac{b}{10^{l_b}}+frac{a}{10^{l_b}(10^{l_a}-1)}tag{3}$$
Because $m$ is not divisible by 2 or 5, we can write $1/m$ as:
$$frac1m=frac{a}{10^{l_a}-1}$$
which means that:
$$frac1n=frac1{2^p5^q} cdot frac1m$$
If we introduce:
$$r=max(p,q)$$
we get:
$$frac1n=frac{2^{r-p}5^{r-q}}{10^r} cdot frac1m=frac{2^{r-p}5^{r-q}a}{10^r(10^{l_a}-1)}tag{4}$$
Now look at (4) carefully.
Case 1:
$$2^{r-p}5^{r-q}a<10^{l_a}-1$$
By comparing (3) and (4), the length of pre-periodic part is $r$, and the pre-periodic part is made of zeroes $b=0$. Periodic part is equal to $2^{r-p}5^{r-q}a$ and the length of the periodic part is $l_a$.
Case 2:
$$2^{r-p}5^{r-q}a>10^{l_a}-1$$
In that case you can write:
$$2^{r-p}5^{r-q}a=s(10^{l_a}-1)+a_1$$
...and (4) becomes:
$$frac1n=frac{s(10^{l_a}-1)+a_1}{10^r(10^{l_a}-1)}=frac{s}{10^r}+frac{a_1}{10^r(10^{l_a}-1)}$$
By comparing the last expression with (4), the length of the pre-periodic part $s$ is again $r$ and the length of repeating sequence $a_1$ is again $l_a$.
Conclusion
- The length of the periodic part in the decimal representation of $1/n$ is determined by the length of periodic part in $1/m$ with $m$ being the greatest divisor of $n$ such that $2nmid m$ and $5nmid m$.
- Pre-periodic part exists only if $n$ is of the form $2^p5^qm$.
- The length of the pre-periodic part is $max(p,q)$
Interesting example
$$frac{1}{19}=0.overline{052631578947368421}$$
Periodic part has 18 digits. Now take a look at:
$$frac{1}{760}=frac{1}{2^3cdot5cdot19}=0.001overline{315789473684210526}$$
Pre-periodic part has length 3 (because the biggest power of 2 or 5 in $n=760$ is 3). And the periodic part has length 18, same length as in $1/19$.
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
add a comment |
Lemma:
For every number $nin N$ that is not divisible by 2 and 5, there exists $kin N$ such that $nmid10^k-1$
Proof: Suppose that the statement is not true, i.e. $10^k-1notequiv0 pmod n$ for all values of $k$. There are infinitely many values of $k$ and just $n-1$ possible values ($1dots n-1$) for $10^k-1pmod n$. So by pidgeon hole principle there are two different values $k_1, k_2$ such that:
$$10^{k_1}-1equiv10^{k_2}-1pmod n,quad (k_1>k_2)$$
This simply means that:
$$10^{k_1}-10^{k_2}equiv0pmod n$$
$$10^{k_2}(10^{k1-k2}-1)equiv0pmod n$$
Number $n$ has no factors 2 and 5 so obviously $nnmid 10^{k_2}$ which implies that $nmid(10^{k_1-k_2}-1)$ or:
$$nmid10^k-1$$
...where $k=k_1-k_2$.
End of lemma proof.
Part 1:
Let us now show that:
For every number $n$ such that $2nmid n$ and $5nmid n$, decimal representation of $1/n$ has no pre-periodic part. In other words, $1/n$ can be written as: $$frac 1n=0.aaadots=0.bar{a}tag{1}$$
...where $a$ stands for a group of repeating digits (possibly starting with zero) of length $l_a$. For example for $n=7$: $1/7=0.overline{142857}$, so $a=142857$ and $l_a=6$.
One can easily show that (1) can be rewritten in the following way:
$${frac1n}=frac{a}{10^{l_a}-1}$$
$$a=frac{10^{l_a}-1}{n}$$
According to our lemma, it's guaranted that there exists $l_a$ such that $nmid 10^{l_a}-1$ so it's is possible to find $a$ for every $n$ such that $1/n=0.bar{a}$, without a pre-periodic part.
Part 2
If $2mid n$ or $5mid n$, decimal representation of $1/n$ has a pre-periodic part:
$$frac1n=0.boverline {a}tag{2}$$
...with the lenght of pre-periodic group of digits $b$ equal to $l_b$ and length of periodic group of digits $a$ equal to $l_a$.
Suppose the pposite, that there is some number $n$ divisible by either 2 or 5 such that:
$$frac1n=0.bar{a}=frac{a}{10^{l_a}-1}$$
$$na=10^{l_a}-1$$
...which is impossible because the LHS is divisible by 2 or 5 and the RHS is clearly not.
Based on part 1 and 2 we now know that:
Decimal representation of $1/n$ has pre-periodic part if and only if $2mid n$ or $5mid n$.
Part 3
For a number $n$ of the form $n=2^p5^qm$ and $2,5nmid m$ the length of pre-periodic part is exactly $max(p,q)$.
It can be easily proved that any number of the form $0.bbar{a}$ can be written as:
$$0.bbar{a}=frac{b}{10^{l_b}}+frac{a}{10^{l_b}(10^{l_a}-1)}tag{3}$$
Because $m$ is not divisible by 2 or 5, we can write $1/m$ as:
$$frac1m=frac{a}{10^{l_a}-1}$$
which means that:
$$frac1n=frac1{2^p5^q} cdot frac1m$$
If we introduce:
$$r=max(p,q)$$
we get:
$$frac1n=frac{2^{r-p}5^{r-q}}{10^r} cdot frac1m=frac{2^{r-p}5^{r-q}a}{10^r(10^{l_a}-1)}tag{4}$$
Now look at (4) carefully.
Case 1:
$$2^{r-p}5^{r-q}a<10^{l_a}-1$$
By comparing (3) and (4), the length of pre-periodic part is $r$, and the pre-periodic part is made of zeroes $b=0$. Periodic part is equal to $2^{r-p}5^{r-q}a$ and the length of the periodic part is $l_a$.
Case 2:
$$2^{r-p}5^{r-q}a>10^{l_a}-1$$
In that case you can write:
$$2^{r-p}5^{r-q}a=s(10^{l_a}-1)+a_1$$
...and (4) becomes:
$$frac1n=frac{s(10^{l_a}-1)+a_1}{10^r(10^{l_a}-1)}=frac{s}{10^r}+frac{a_1}{10^r(10^{l_a}-1)}$$
By comparing the last expression with (4), the length of the pre-periodic part $s$ is again $r$ and the length of repeating sequence $a_1$ is again $l_a$.
Conclusion
- The length of the periodic part in the decimal representation of $1/n$ is determined by the length of periodic part in $1/m$ with $m$ being the greatest divisor of $n$ such that $2nmid m$ and $5nmid m$.
- Pre-periodic part exists only if $n$ is of the form $2^p5^qm$.
- The length of the pre-periodic part is $max(p,q)$
Interesting example
$$frac{1}{19}=0.overline{052631578947368421}$$
Periodic part has 18 digits. Now take a look at:
$$frac{1}{760}=frac{1}{2^3cdot5cdot19}=0.001overline{315789473684210526}$$
Pre-periodic part has length 3 (because the biggest power of 2 or 5 in $n=760$ is 3). And the periodic part has length 18, same length as in $1/19$.
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
add a comment |
Lemma:
For every number $nin N$ that is not divisible by 2 and 5, there exists $kin N$ such that $nmid10^k-1$
Proof: Suppose that the statement is not true, i.e. $10^k-1notequiv0 pmod n$ for all values of $k$. There are infinitely many values of $k$ and just $n-1$ possible values ($1dots n-1$) for $10^k-1pmod n$. So by pidgeon hole principle there are two different values $k_1, k_2$ such that:
$$10^{k_1}-1equiv10^{k_2}-1pmod n,quad (k_1>k_2)$$
This simply means that:
$$10^{k_1}-10^{k_2}equiv0pmod n$$
$$10^{k_2}(10^{k1-k2}-1)equiv0pmod n$$
Number $n$ has no factors 2 and 5 so obviously $nnmid 10^{k_2}$ which implies that $nmid(10^{k_1-k_2}-1)$ or:
$$nmid10^k-1$$
...where $k=k_1-k_2$.
End of lemma proof.
Part 1:
Let us now show that:
For every number $n$ such that $2nmid n$ and $5nmid n$, decimal representation of $1/n$ has no pre-periodic part. In other words, $1/n$ can be written as: $$frac 1n=0.aaadots=0.bar{a}tag{1}$$
...where $a$ stands for a group of repeating digits (possibly starting with zero) of length $l_a$. For example for $n=7$: $1/7=0.overline{142857}$, so $a=142857$ and $l_a=6$.
One can easily show that (1) can be rewritten in the following way:
$${frac1n}=frac{a}{10^{l_a}-1}$$
$$a=frac{10^{l_a}-1}{n}$$
According to our lemma, it's guaranted that there exists $l_a$ such that $nmid 10^{l_a}-1$ so it's is possible to find $a$ for every $n$ such that $1/n=0.bar{a}$, without a pre-periodic part.
Part 2
If $2mid n$ or $5mid n$, decimal representation of $1/n$ has a pre-periodic part:
$$frac1n=0.boverline {a}tag{2}$$
...with the lenght of pre-periodic group of digits $b$ equal to $l_b$ and length of periodic group of digits $a$ equal to $l_a$.
Suppose the pposite, that there is some number $n$ divisible by either 2 or 5 such that:
$$frac1n=0.bar{a}=frac{a}{10^{l_a}-1}$$
$$na=10^{l_a}-1$$
...which is impossible because the LHS is divisible by 2 or 5 and the RHS is clearly not.
Based on part 1 and 2 we now know that:
Decimal representation of $1/n$ has pre-periodic part if and only if $2mid n$ or $5mid n$.
Part 3
For a number $n$ of the form $n=2^p5^qm$ and $2,5nmid m$ the length of pre-periodic part is exactly $max(p,q)$.
It can be easily proved that any number of the form $0.bbar{a}$ can be written as:
$$0.bbar{a}=frac{b}{10^{l_b}}+frac{a}{10^{l_b}(10^{l_a}-1)}tag{3}$$
Because $m$ is not divisible by 2 or 5, we can write $1/m$ as:
$$frac1m=frac{a}{10^{l_a}-1}$$
which means that:
$$frac1n=frac1{2^p5^q} cdot frac1m$$
If we introduce:
$$r=max(p,q)$$
we get:
$$frac1n=frac{2^{r-p}5^{r-q}}{10^r} cdot frac1m=frac{2^{r-p}5^{r-q}a}{10^r(10^{l_a}-1)}tag{4}$$
Now look at (4) carefully.
Case 1:
$$2^{r-p}5^{r-q}a<10^{l_a}-1$$
By comparing (3) and (4), the length of pre-periodic part is $r$, and the pre-periodic part is made of zeroes $b=0$. Periodic part is equal to $2^{r-p}5^{r-q}a$ and the length of the periodic part is $l_a$.
Case 2:
$$2^{r-p}5^{r-q}a>10^{l_a}-1$$
In that case you can write:
$$2^{r-p}5^{r-q}a=s(10^{l_a}-1)+a_1$$
...and (4) becomes:
$$frac1n=frac{s(10^{l_a}-1)+a_1}{10^r(10^{l_a}-1)}=frac{s}{10^r}+frac{a_1}{10^r(10^{l_a}-1)}$$
By comparing the last expression with (4), the length of the pre-periodic part $s$ is again $r$ and the length of repeating sequence $a_1$ is again $l_a$.
Conclusion
- The length of the periodic part in the decimal representation of $1/n$ is determined by the length of periodic part in $1/m$ with $m$ being the greatest divisor of $n$ such that $2nmid m$ and $5nmid m$.
- Pre-periodic part exists only if $n$ is of the form $2^p5^qm$.
- The length of the pre-periodic part is $max(p,q)$
Interesting example
$$frac{1}{19}=0.overline{052631578947368421}$$
Periodic part has 18 digits. Now take a look at:
$$frac{1}{760}=frac{1}{2^3cdot5cdot19}=0.001overline{315789473684210526}$$
Pre-periodic part has length 3 (because the biggest power of 2 or 5 in $n=760$ is 3). And the periodic part has length 18, same length as in $1/19$.
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
Lemma:
For every number $nin N$ that is not divisible by 2 and 5, there exists $kin N$ such that $nmid10^k-1$
Proof: Suppose that the statement is not true, i.e. $10^k-1notequiv0 pmod n$ for all values of $k$. There are infinitely many values of $k$ and just $n-1$ possible values ($1dots n-1$) for $10^k-1pmod n$. So by pidgeon hole principle there are two different values $k_1, k_2$ such that:
$$10^{k_1}-1equiv10^{k_2}-1pmod n,quad (k_1>k_2)$$
This simply means that:
$$10^{k_1}-10^{k_2}equiv0pmod n$$
$$10^{k_2}(10^{k1-k2}-1)equiv0pmod n$$
Number $n$ has no factors 2 and 5 so obviously $nnmid 10^{k_2}$ which implies that $nmid(10^{k_1-k_2}-1)$ or:
$$nmid10^k-1$$
...where $k=k_1-k_2$.
End of lemma proof.
Part 1:
Let us now show that:
For every number $n$ such that $2nmid n$ and $5nmid n$, decimal representation of $1/n$ has no pre-periodic part. In other words, $1/n$ can be written as: $$frac 1n=0.aaadots=0.bar{a}tag{1}$$
...where $a$ stands for a group of repeating digits (possibly starting with zero) of length $l_a$. For example for $n=7$: $1/7=0.overline{142857}$, so $a=142857$ and $l_a=6$.
One can easily show that (1) can be rewritten in the following way:
$${frac1n}=frac{a}{10^{l_a}-1}$$
$$a=frac{10^{l_a}-1}{n}$$
According to our lemma, it's guaranted that there exists $l_a$ such that $nmid 10^{l_a}-1$ so it's is possible to find $a$ for every $n$ such that $1/n=0.bar{a}$, without a pre-periodic part.
Part 2
If $2mid n$ or $5mid n$, decimal representation of $1/n$ has a pre-periodic part:
$$frac1n=0.boverline {a}tag{2}$$
...with the lenght of pre-periodic group of digits $b$ equal to $l_b$ and length of periodic group of digits $a$ equal to $l_a$.
Suppose the pposite, that there is some number $n$ divisible by either 2 or 5 such that:
$$frac1n=0.bar{a}=frac{a}{10^{l_a}-1}$$
$$na=10^{l_a}-1$$
...which is impossible because the LHS is divisible by 2 or 5 and the RHS is clearly not.
Based on part 1 and 2 we now know that:
Decimal representation of $1/n$ has pre-periodic part if and only if $2mid n$ or $5mid n$.
Part 3
For a number $n$ of the form $n=2^p5^qm$ and $2,5nmid m$ the length of pre-periodic part is exactly $max(p,q)$.
It can be easily proved that any number of the form $0.bbar{a}$ can be written as:
$$0.bbar{a}=frac{b}{10^{l_b}}+frac{a}{10^{l_b}(10^{l_a}-1)}tag{3}$$
Because $m$ is not divisible by 2 or 5, we can write $1/m$ as:
$$frac1m=frac{a}{10^{l_a}-1}$$
which means that:
$$frac1n=frac1{2^p5^q} cdot frac1m$$
If we introduce:
$$r=max(p,q)$$
we get:
$$frac1n=frac{2^{r-p}5^{r-q}}{10^r} cdot frac1m=frac{2^{r-p}5^{r-q}a}{10^r(10^{l_a}-1)}tag{4}$$
Now look at (4) carefully.
Case 1:
$$2^{r-p}5^{r-q}a<10^{l_a}-1$$
By comparing (3) and (4), the length of pre-periodic part is $r$, and the pre-periodic part is made of zeroes $b=0$. Periodic part is equal to $2^{r-p}5^{r-q}a$ and the length of the periodic part is $l_a$.
Case 2:
$$2^{r-p}5^{r-q}a>10^{l_a}-1$$
In that case you can write:
$$2^{r-p}5^{r-q}a=s(10^{l_a}-1)+a_1$$
...and (4) becomes:
$$frac1n=frac{s(10^{l_a}-1)+a_1}{10^r(10^{l_a}-1)}=frac{s}{10^r}+frac{a_1}{10^r(10^{l_a}-1)}$$
By comparing the last expression with (4), the length of the pre-periodic part $s$ is again $r$ and the length of repeating sequence $a_1$ is again $l_a$.
Conclusion
- The length of the periodic part in the decimal representation of $1/n$ is determined by the length of periodic part in $1/m$ with $m$ being the greatest divisor of $n$ such that $2nmid m$ and $5nmid m$.
- Pre-periodic part exists only if $n$ is of the form $2^p5^qm$.
- The length of the pre-periodic part is $max(p,q)$
Interesting example
$$frac{1}{19}=0.overline{052631578947368421}$$
Periodic part has 18 digits. Now take a look at:
$$frac{1}{760}=frac{1}{2^3cdot5cdot19}=0.001overline{315789473684210526}$$
Pre-periodic part has length 3 (because the biggest power of 2 or 5 in $n=760$ is 3). And the periodic part has length 18, same length as in $1/19$.
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
edited Jan 2 at 10:31
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
answered Jan 2 at 9:07
OldboyOldboy
7,1391832
7,1391832
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
add a comment |
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
I have a question: Are part $1$ and $2$ really necessary? Because stating that the length of the non-periodic part of $1/n$ if $ n = 2^m5^n p$ is $max(m,n)$ also takes care of the situations where $n$ is not at all divisible by $2$ and $5$, in which case $max(m,n)=0$ and so no non-periodic part.
– Anu Radha
Jan 7 at 18:52
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057935%2frecurring-decimal-expansion%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
Leading question: can you prove that if $n$ is divisible by neither $2$ nor $5$, then the decimal fraction is immediately periodic (that is, the length of the non-periodic part is $0$)? (By the way, the standard name for that part is the "pre-periodic" part.)
– Greg Martin
Dec 31 '18 at 18:51
1
Take the examples of $frac{1}{3}=0.3333333...$, f $frac{1}{7}=0.142857142857...$, and $frac{1}{11}=0.09090909090909...$. If $n$ is not divisible by $2$ or $5$, the pre-periodic length will always be zero.
– poetasis
Dec 31 '18 at 19:33
1
@GregMartin, It actually seemed intuitive for me, but I’m not able to come up with a rigorous proof for that. (Well, actually, every step of the solution seems very intuitive, but I don’t know how to write a rigorous solution by giving proofs for them :/ )
– Anu Radha
Jan 1 at 3:50
1
By the way, is there any way I can rigorously prove that the the length of the pre-periodic part is related to powers of $2$ and $5$? Because, if powers of any other prime are not going to affect the length of the pre- periodic part, then powers of $2$ or $5$ might have some relation with its length, right?
– Anu Radha
Jan 1 at 15:30
2
Yes, the length of the pre-periodic part is definitely going to be determined by the powers of $2$ and $5$! Do you know modular arithmetic? Do you know what the "order of $a$ modulo $n$" is? Because knowing that the period of $1/n$ is actually equal to the order of $10$ modulo $n$ (when $n$ is not divisible by $2$ or $5$) makes the periodicity easier to prove.
– Greg Martin
Jan 1 at 20:01