Proof that the base 10 representation of a positive integer is uniqueIs there an easy way to see that binary expansion is unique?Find the missing digit in a multiple of 48Proof that an odd integer multiplied by $3$ and squared is always oddProof of $6174$ as the unique 4-digit Kaprekar's constantproof - any positive integer can be uniquely expressed as $a = 3^m + 3^m-1b_m-1 + cdots + 3^0b^0$Does anyone know a reference to best-fitting lines with integral coefficients?Explanation on the Proof that every integer greater than one may be used as a baseProve $ 4times 2^n $ divides $ a^2^n-1 $ for all odd a, and $ n in Bbb N $Prove that an integer which divides $p^t$ must equal $p^k$ for some k, $1leq kleq t$Proof: Given that $x$ is a positive integer, prove…Prove that every positive integer $m$ can be written in 'base factorial' form
What is the offset in a seaplane's hull?
Concept of linear mappings are confusing me
Can I interfere when another PC is about to be attacked?
XeLaTeX and pdfLaTeX ignore hyphenation
Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).
What does "enim et" mean?
What is the meaning of "of trouble" in the following sentence?
Is there really no realistic way for a skeleton monster to move around without magic?
how to create a data type and make it available in all Databases?
Example of a relative pronoun
A Journey Through Space and Time
How to make payment on the internet without leaving a money trail?
What is the logic behind how bash tests for true/false?
Circuitry of TV splitters
Are tax years 2016 & 2017 back taxes deductible for tax year 2018?
How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)
Motorized valve interfering with button?
How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?
Chess with symmetric move-square
How do I create uniquely male characters?
Can Medicine checks be used, with decent rolls, to completely mitigate the risk of death from ongoing damage?
If Manufacturer spice model and Datasheet give different values which should I use?
Shell script can be run only with sh command
Could a US political party gain complete control over the government by removing checks & balances?
Proof that the base 10 representation of a positive integer is unique
Is there an easy way to see that binary expansion is unique?Find the missing digit in a multiple of 48Proof that an odd integer multiplied by $3$ and squared is always oddProof of $6174$ as the unique 4-digit Kaprekar's constantproof - any positive integer can be uniquely expressed as $a = 3^m + 3^m-1b_m-1 + cdots + 3^0b^0$Does anyone know a reference to best-fitting lines with integral coefficients?Explanation on the Proof that every integer greater than one may be used as a baseProve $ 4times 2^n $ divides $ a^2^n-1 $ for all odd a, and $ n in Bbb N $Prove that an integer which divides $p^t$ must equal $p^k$ for some k, $1leq kleq t$Proof: Given that $x$ is a positive integer, prove…Prove that every positive integer $m$ can be written in 'base factorial' form
$begingroup$
Proposition: Let n $in$ N. If $n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $ where $p,q, in Z_geq0$, each $x_i$ and each $y_i$ is a digit, $x_pneq0$ and $y_qneq0$,
then $p=q$, and $x_i = y_i$ for all i
So far I have:
$n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $
$sum_i=0^p x_i = sum_i=0^qy_i $
$sum_i=0^p x_i - sum_i=0^qy_i = 0$
I feel like I can perform some summation algebra to write this as one summation, but I'm not sure how.
How do I prove that $p=q$ and the sequence $x_i = y_i$ ?
elementary-number-theory
$endgroup$
add a comment |
$begingroup$
Proposition: Let n $in$ N. If $n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $ where $p,q, in Z_geq0$, each $x_i$ and each $y_i$ is a digit, $x_pneq0$ and $y_qneq0$,
then $p=q$, and $x_i = y_i$ for all i
So far I have:
$n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $
$sum_i=0^p x_i = sum_i=0^qy_i $
$sum_i=0^p x_i - sum_i=0^qy_i = 0$
I feel like I can perform some summation algebra to write this as one summation, but I'm not sure how.
How do I prove that $p=q$ and the sequence $x_i = y_i$ ?
elementary-number-theory
$endgroup$
2
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54
add a comment |
$begingroup$
Proposition: Let n $in$ N. If $n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $ where $p,q, in Z_geq0$, each $x_i$ and each $y_i$ is a digit, $x_pneq0$ and $y_qneq0$,
then $p=q$, and $x_i = y_i$ for all i
So far I have:
$n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $
$sum_i=0^p x_i = sum_i=0^qy_i $
$sum_i=0^p x_i - sum_i=0^qy_i = 0$
I feel like I can perform some summation algebra to write this as one summation, but I'm not sure how.
How do I prove that $p=q$ and the sequence $x_i = y_i$ ?
elementary-number-theory
$endgroup$
Proposition: Let n $in$ N. If $n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $ where $p,q, in Z_geq0$, each $x_i$ and each $y_i$ is a digit, $x_pneq0$ and $y_qneq0$,
then $p=q$, and $x_i = y_i$ for all i
So far I have:
$n = sum_i=0^p x_i10^i = sum_i=0^qy_i10^i $
$sum_i=0^p x_i = sum_i=0^qy_i $
$sum_i=0^p x_i - sum_i=0^qy_i = 0$
I feel like I can perform some summation algebra to write this as one summation, but I'm not sure how.
How do I prove that $p=q$ and the sequence $x_i = y_i$ ?
elementary-number-theory
elementary-number-theory
asked Mar 29 at 22:29
beepbeepboop123123beepbeepboop123123
536
536
2
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54
add a comment |
2
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54
2
2
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The key issue with the base $10$ representation being unique is that the digits are restricted to being between $0$ and $9$ inclusive (note that without this limitation, the representations may not necessarily be unique). The main reason this is important is that the difference in digits is limited to being between $-9$ and $9$, inclusive. To see why this is important, consider what you've stated, i.e.,
$$n = sum_i=0^p x_i 10^i = sum_i=0^q y_i 10^i tag1labeleq1$$
where $p,q, in Z_geq 0$, each $x_i$ & $y_i$ is a digit of $0$ to $9$, $x_p neq 0$ and $y_q neq 0$. To make it a bit easier for processing in case $p neq q$, let $r = max(p,q)$ and extend $x_i$ to be $0$ for any $i gt p$ and $y_i$ to be $0$ for any $i gt q$, so eqrefeq1 becomes
$$n = sum_i=0^r x_i 10^i = sum_i=0^r y_i 10^i tag2labeleq2$$
Subtracting the middle & LHS parts of eqrefeq2 gives
$$0 = sum_i = 0^r left(x_i - y_iright) 10^i tag3labeleq3$$
If $x_i neq y_i$ for one or more $i$, let $k$ be the smallest one. Thus, for all $i lt k$, $x_i = y_i$ so $x_i - y_i = 0$, causing those terms to all become $0$. They can therefore be ignored, simplifying eqrefeq3 to
$$0 = sum_i = k^r left(x_i - y_iright) 10^i tag4labeleq4$$
Next, dividing both sides by $10^k$ gives
$$0 = sum_i = k^r left(x_i - y_iright) 10^i - k tag5labeleq5$$
Note that all of the terms on the RHS of eqrefeq5 have at least one factor of $10$ except for the first one. Since $10$ divides $0$, plus all of the terms on the RHS of eqrefeq5 after the first term, this means the first term of $left(x_k - y_kright)10^0 = x_k - y_k$ must be a multiple of $10$. Since $-9 le x_k - y_k le 9$, this means that $x_k - y_k = 0$, i.e., $x_k = y_k$, so they can't be different. This contradicts the assumption that there is at least one digit different, thus showing that all of the digits up to $r$ are the same. This also means the highest non-zero ones must be the same, i.e., $p = q$.
This same basic argument can be used to show that an integer can be uniquely represented in any base $b ge 2$ as long as the digits used are in the range of $0$ to $b - 1$, inclusive (e.g., binary using $0$ and $1$, or hexadecimal using $0$ to $F$).
$endgroup$
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
add a comment |
$begingroup$
Rather the proving any two representations on $N$ must be equal, try proving $N$ has exactly one unique representation.
But the division theorem, for any integer $N$ the are are unique integers $M_1$ and $x_0$ so that $N = 10M_1 + x_0; 0 le x_0 < 10$. This proves that $x_0$ must be uniquely determined.
Inductively for each $M_k$ there are unique $M_k+1$ and $x_k$ so that $M_k = 10M_k+1 + x_k; 0le x_k < 10$.
And that's it really. As $N$ is bounded above by some $10^p+1$ this will have a finite number of steps.
$endgroup$
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%2f3167706%2fproof-that-the-base-10-representation-of-a-positive-integer-is-unique%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The key issue with the base $10$ representation being unique is that the digits are restricted to being between $0$ and $9$ inclusive (note that without this limitation, the representations may not necessarily be unique). The main reason this is important is that the difference in digits is limited to being between $-9$ and $9$, inclusive. To see why this is important, consider what you've stated, i.e.,
$$n = sum_i=0^p x_i 10^i = sum_i=0^q y_i 10^i tag1labeleq1$$
where $p,q, in Z_geq 0$, each $x_i$ & $y_i$ is a digit of $0$ to $9$, $x_p neq 0$ and $y_q neq 0$. To make it a bit easier for processing in case $p neq q$, let $r = max(p,q)$ and extend $x_i$ to be $0$ for any $i gt p$ and $y_i$ to be $0$ for any $i gt q$, so eqrefeq1 becomes
$$n = sum_i=0^r x_i 10^i = sum_i=0^r y_i 10^i tag2labeleq2$$
Subtracting the middle & LHS parts of eqrefeq2 gives
$$0 = sum_i = 0^r left(x_i - y_iright) 10^i tag3labeleq3$$
If $x_i neq y_i$ for one or more $i$, let $k$ be the smallest one. Thus, for all $i lt k$, $x_i = y_i$ so $x_i - y_i = 0$, causing those terms to all become $0$. They can therefore be ignored, simplifying eqrefeq3 to
$$0 = sum_i = k^r left(x_i - y_iright) 10^i tag4labeleq4$$
Next, dividing both sides by $10^k$ gives
$$0 = sum_i = k^r left(x_i - y_iright) 10^i - k tag5labeleq5$$
Note that all of the terms on the RHS of eqrefeq5 have at least one factor of $10$ except for the first one. Since $10$ divides $0$, plus all of the terms on the RHS of eqrefeq5 after the first term, this means the first term of $left(x_k - y_kright)10^0 = x_k - y_k$ must be a multiple of $10$. Since $-9 le x_k - y_k le 9$, this means that $x_k - y_k = 0$, i.e., $x_k = y_k$, so they can't be different. This contradicts the assumption that there is at least one digit different, thus showing that all of the digits up to $r$ are the same. This also means the highest non-zero ones must be the same, i.e., $p = q$.
This same basic argument can be used to show that an integer can be uniquely represented in any base $b ge 2$ as long as the digits used are in the range of $0$ to $b - 1$, inclusive (e.g., binary using $0$ and $1$, or hexadecimal using $0$ to $F$).
$endgroup$
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
add a comment |
$begingroup$
The key issue with the base $10$ representation being unique is that the digits are restricted to being between $0$ and $9$ inclusive (note that without this limitation, the representations may not necessarily be unique). The main reason this is important is that the difference in digits is limited to being between $-9$ and $9$, inclusive. To see why this is important, consider what you've stated, i.e.,
$$n = sum_i=0^p x_i 10^i = sum_i=0^q y_i 10^i tag1labeleq1$$
where $p,q, in Z_geq 0$, each $x_i$ & $y_i$ is a digit of $0$ to $9$, $x_p neq 0$ and $y_q neq 0$. To make it a bit easier for processing in case $p neq q$, let $r = max(p,q)$ and extend $x_i$ to be $0$ for any $i gt p$ and $y_i$ to be $0$ for any $i gt q$, so eqrefeq1 becomes
$$n = sum_i=0^r x_i 10^i = sum_i=0^r y_i 10^i tag2labeleq2$$
Subtracting the middle & LHS parts of eqrefeq2 gives
$$0 = sum_i = 0^r left(x_i - y_iright) 10^i tag3labeleq3$$
If $x_i neq y_i$ for one or more $i$, let $k$ be the smallest one. Thus, for all $i lt k$, $x_i = y_i$ so $x_i - y_i = 0$, causing those terms to all become $0$. They can therefore be ignored, simplifying eqrefeq3 to
$$0 = sum_i = k^r left(x_i - y_iright) 10^i tag4labeleq4$$
Next, dividing both sides by $10^k$ gives
$$0 = sum_i = k^r left(x_i - y_iright) 10^i - k tag5labeleq5$$
Note that all of the terms on the RHS of eqrefeq5 have at least one factor of $10$ except for the first one. Since $10$ divides $0$, plus all of the terms on the RHS of eqrefeq5 after the first term, this means the first term of $left(x_k - y_kright)10^0 = x_k - y_k$ must be a multiple of $10$. Since $-9 le x_k - y_k le 9$, this means that $x_k - y_k = 0$, i.e., $x_k = y_k$, so they can't be different. This contradicts the assumption that there is at least one digit different, thus showing that all of the digits up to $r$ are the same. This also means the highest non-zero ones must be the same, i.e., $p = q$.
This same basic argument can be used to show that an integer can be uniquely represented in any base $b ge 2$ as long as the digits used are in the range of $0$ to $b - 1$, inclusive (e.g., binary using $0$ and $1$, or hexadecimal using $0$ to $F$).
$endgroup$
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
add a comment |
$begingroup$
The key issue with the base $10$ representation being unique is that the digits are restricted to being between $0$ and $9$ inclusive (note that without this limitation, the representations may not necessarily be unique). The main reason this is important is that the difference in digits is limited to being between $-9$ and $9$, inclusive. To see why this is important, consider what you've stated, i.e.,
$$n = sum_i=0^p x_i 10^i = sum_i=0^q y_i 10^i tag1labeleq1$$
where $p,q, in Z_geq 0$, each $x_i$ & $y_i$ is a digit of $0$ to $9$, $x_p neq 0$ and $y_q neq 0$. To make it a bit easier for processing in case $p neq q$, let $r = max(p,q)$ and extend $x_i$ to be $0$ for any $i gt p$ and $y_i$ to be $0$ for any $i gt q$, so eqrefeq1 becomes
$$n = sum_i=0^r x_i 10^i = sum_i=0^r y_i 10^i tag2labeleq2$$
Subtracting the middle & LHS parts of eqrefeq2 gives
$$0 = sum_i = 0^r left(x_i - y_iright) 10^i tag3labeleq3$$
If $x_i neq y_i$ for one or more $i$, let $k$ be the smallest one. Thus, for all $i lt k$, $x_i = y_i$ so $x_i - y_i = 0$, causing those terms to all become $0$. They can therefore be ignored, simplifying eqrefeq3 to
$$0 = sum_i = k^r left(x_i - y_iright) 10^i tag4labeleq4$$
Next, dividing both sides by $10^k$ gives
$$0 = sum_i = k^r left(x_i - y_iright) 10^i - k tag5labeleq5$$
Note that all of the terms on the RHS of eqrefeq5 have at least one factor of $10$ except for the first one. Since $10$ divides $0$, plus all of the terms on the RHS of eqrefeq5 after the first term, this means the first term of $left(x_k - y_kright)10^0 = x_k - y_k$ must be a multiple of $10$. Since $-9 le x_k - y_k le 9$, this means that $x_k - y_k = 0$, i.e., $x_k = y_k$, so they can't be different. This contradicts the assumption that there is at least one digit different, thus showing that all of the digits up to $r$ are the same. This also means the highest non-zero ones must be the same, i.e., $p = q$.
This same basic argument can be used to show that an integer can be uniquely represented in any base $b ge 2$ as long as the digits used are in the range of $0$ to $b - 1$, inclusive (e.g., binary using $0$ and $1$, or hexadecimal using $0$ to $F$).
$endgroup$
The key issue with the base $10$ representation being unique is that the digits are restricted to being between $0$ and $9$ inclusive (note that without this limitation, the representations may not necessarily be unique). The main reason this is important is that the difference in digits is limited to being between $-9$ and $9$, inclusive. To see why this is important, consider what you've stated, i.e.,
$$n = sum_i=0^p x_i 10^i = sum_i=0^q y_i 10^i tag1labeleq1$$
where $p,q, in Z_geq 0$, each $x_i$ & $y_i$ is a digit of $0$ to $9$, $x_p neq 0$ and $y_q neq 0$. To make it a bit easier for processing in case $p neq q$, let $r = max(p,q)$ and extend $x_i$ to be $0$ for any $i gt p$ and $y_i$ to be $0$ for any $i gt q$, so eqrefeq1 becomes
$$n = sum_i=0^r x_i 10^i = sum_i=0^r y_i 10^i tag2labeleq2$$
Subtracting the middle & LHS parts of eqrefeq2 gives
$$0 = sum_i = 0^r left(x_i - y_iright) 10^i tag3labeleq3$$
If $x_i neq y_i$ for one or more $i$, let $k$ be the smallest one. Thus, for all $i lt k$, $x_i = y_i$ so $x_i - y_i = 0$, causing those terms to all become $0$. They can therefore be ignored, simplifying eqrefeq3 to
$$0 = sum_i = k^r left(x_i - y_iright) 10^i tag4labeleq4$$
Next, dividing both sides by $10^k$ gives
$$0 = sum_i = k^r left(x_i - y_iright) 10^i - k tag5labeleq5$$
Note that all of the terms on the RHS of eqrefeq5 have at least one factor of $10$ except for the first one. Since $10$ divides $0$, plus all of the terms on the RHS of eqrefeq5 after the first term, this means the first term of $left(x_k - y_kright)10^0 = x_k - y_k$ must be a multiple of $10$. Since $-9 le x_k - y_k le 9$, this means that $x_k - y_k = 0$, i.e., $x_k = y_k$, so they can't be different. This contradicts the assumption that there is at least one digit different, thus showing that all of the digits up to $r$ are the same. This also means the highest non-zero ones must be the same, i.e., $p = q$.
This same basic argument can be used to show that an integer can be uniquely represented in any base $b ge 2$ as long as the digits used are in the range of $0$ to $b - 1$, inclusive (e.g., binary using $0$ and $1$, or hexadecimal using $0$ to $F$).
edited Mar 31 at 21:06
answered Mar 30 at 1:40
John OmielanJohn Omielan
4,7612215
4,7612215
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
add a comment |
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
If $xi≠yi$ for one or more i, let k be the smallest one. Thus, all lower differences will be 0... What do you mean by all the lower differences will be 0?
$endgroup$
– beepbeepboop123123
Mar 31 at 20:45
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 Since $k$ is the smallest value of $i$ where $x_i neq y_i$, then for all $i$ (if any) less than $k$, we have that $x_i = y_i$, so $x_i - y_i = 0$, i.e., the differences are $0$.
$endgroup$
– John Omielan
Mar 31 at 20:49
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
$begingroup$
@beepbeepboop123123 I used the term "lower" to mean for all smaller indices, but that wasn't clear to you, so I've updated my answer to try to explain that section more clearly.
$endgroup$
– John Omielan
Mar 31 at 21:08
add a comment |
$begingroup$
Rather the proving any two representations on $N$ must be equal, try proving $N$ has exactly one unique representation.
But the division theorem, for any integer $N$ the are are unique integers $M_1$ and $x_0$ so that $N = 10M_1 + x_0; 0 le x_0 < 10$. This proves that $x_0$ must be uniquely determined.
Inductively for each $M_k$ there are unique $M_k+1$ and $x_k$ so that $M_k = 10M_k+1 + x_k; 0le x_k < 10$.
And that's it really. As $N$ is bounded above by some $10^p+1$ this will have a finite number of steps.
$endgroup$
add a comment |
$begingroup$
Rather the proving any two representations on $N$ must be equal, try proving $N$ has exactly one unique representation.
But the division theorem, for any integer $N$ the are are unique integers $M_1$ and $x_0$ so that $N = 10M_1 + x_0; 0 le x_0 < 10$. This proves that $x_0$ must be uniquely determined.
Inductively for each $M_k$ there are unique $M_k+1$ and $x_k$ so that $M_k = 10M_k+1 + x_k; 0le x_k < 10$.
And that's it really. As $N$ is bounded above by some $10^p+1$ this will have a finite number of steps.
$endgroup$
add a comment |
$begingroup$
Rather the proving any two representations on $N$ must be equal, try proving $N$ has exactly one unique representation.
But the division theorem, for any integer $N$ the are are unique integers $M_1$ and $x_0$ so that $N = 10M_1 + x_0; 0 le x_0 < 10$. This proves that $x_0$ must be uniquely determined.
Inductively for each $M_k$ there are unique $M_k+1$ and $x_k$ so that $M_k = 10M_k+1 + x_k; 0le x_k < 10$.
And that's it really. As $N$ is bounded above by some $10^p+1$ this will have a finite number of steps.
$endgroup$
Rather the proving any two representations on $N$ must be equal, try proving $N$ has exactly one unique representation.
But the division theorem, for any integer $N$ the are are unique integers $M_1$ and $x_0$ so that $N = 10M_1 + x_0; 0 le x_0 < 10$. This proves that $x_0$ must be uniquely determined.
Inductively for each $M_k$ there are unique $M_k+1$ and $x_k$ so that $M_k = 10M_k+1 + x_k; 0le x_k < 10$.
And that's it really. As $N$ is bounded above by some $10^p+1$ this will have a finite number of steps.
answered Mar 30 at 2:44
fleabloodfleablood
73.8k22891
73.8k22891
add a comment |
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%2f3167706%2fproof-that-the-base-10-representation-of-a-positive-integer-is-unique%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
2
$begingroup$
Proof by contradiction, find the first difference, show that its impossible.
$endgroup$
– Don Thousand
Mar 29 at 22:30
$begingroup$
Let $x = sumlimits_i=0^px_i10^i$ and $y=sumlimits_i=0^q y_i 10^i$. To show $p=q$: supposing that $q > p$, can you work out the minimum possible value of $y$ and the maximum possible value of $x$ and hence show that $y > x$ (so $yne x$)? (It might help if you think in terms of specific numbers a bit: "clearly" a $4$ digit number is greater than any $3$ digit number for example, since a $4$ digit number is at least $1000$ and a $3$ digit number is at most $999$.)
$endgroup$
– Minus One-Twelfth
Mar 29 at 22:33
$begingroup$
This is a little confusing to me; I tried going along this path and I proved that the last term of each of the different sums, are unequal to each other. How does this help proving p = q and $x_i = y_i$?
$endgroup$
– beepbeepboop123123
Mar 30 at 0:54
$begingroup$
As you well know, the proof won’t be too much good for infinite expansions. How were you planning to use it to get to the claim in your title ?
$endgroup$
– Lubin
Mar 30 at 1:49
$begingroup$
Possible duplicate: math.stackexchange.com/questions/3017323/…
$endgroup$
– Ethan Bolker
Mar 30 at 2:54