Fus Ro Dah
Member
- Joined
- Dec 16, 2011
- Messages
- 248
- Gender
- Male
- HSC
- 2013
-
Looking for HSC notes and resources? Check out our Notes & Resources page
Stubborn Number. (1 Viewer)
- Thread starter Fus Ro Dah
- Start date
If I understand the question correctly, and it's asking if there are any numbers for which every multiple has a 0,1,2...,9 in it somewhere, then I think the answer is no.
We can do this constructively and actually show that every positive integer has infinitely many multiples which contain only 0 and one other digit.
So to do this, let us start with any number A. If A is coprime with 10, then let n be the order of 10 modulo A - Since 10^n, 10^2n ... 10^An are all congruent to 1 modulo A then, we know the sum from k=1 to A of 10^kn is a number congruent to 0 mod A (Since there are A things in the summand all congruent to 1 mod A) that contains only 0s and ones in its decimal expansion, so A can't be stubborn. (Also we could take 2 times that sum, or 3 or 4 etc. to get a multiple that has 0s and anything else from 2 to 9 as the only digit if we wanted, and we could also take bigger multiple of n in the exponent to generate infinitely many counterexamples.)
Now if A isn't coprime to 10, let A' be the largest factor of A that is coprime to 10. Clearly A' has some non-stubborn multiple as earlier, so let this be B. Then 10^r * B for large enough r must be a multiple of A that has only 0s and 1s again, as you've put back in all the powers of 2 and 5 you could possibly be deficient just by adding 0s to the end of the number.
I.e. for the number you gave, drop the 0 off the end, find the multiple of the smaller thing that has only 0s and 1s, then just multiply by 10 again and you've found some multiple that breaks the stubbornness.
We can do this constructively and actually show that every positive integer has infinitely many multiples which contain only 0 and one other digit.
So to do this, let us start with any number A. If A is coprime with 10, then let n be the order of 10 modulo A - Since 10^n, 10^2n ... 10^An are all congruent to 1 modulo A then, we know the sum from k=1 to A of 10^kn is a number congruent to 0 mod A (Since there are A things in the summand all congruent to 1 mod A) that contains only 0s and ones in its decimal expansion, so A can't be stubborn. (Also we could take 2 times that sum, or 3 or 4 etc. to get a multiple that has 0s and anything else from 2 to 9 as the only digit if we wanted, and we could also take bigger multiple of n in the exponent to generate infinitely many counterexamples.)
Now if A isn't coprime to 10, let A' be the largest factor of A that is coprime to 10. Clearly A' has some non-stubborn multiple as earlier, so let this be B. Then 10^r * B for large enough r must be a multiple of A that has only 0s and 1s again, as you've put back in all the powers of 2 and 5 you could possibly be deficient just by adding 0s to the end of the number.
I.e. for the number you gave, drop the 0 off the end, find the multiple of the smaller thing that has only 0s and 1s, then just multiply by 10 again and you've found some multiple that breaks the stubbornness.
Fus Ro Dah
Member
- Joined
- Dec 16, 2011
- Messages
- 248
- Gender
- Male
- HSC
- 2013
Your answer is correct. The 'one other digit' I used was simply 9. My proof is similar to yours, but uses Euler's Totient Theorem.
Suppose N is stubborn. Then
, where M is coprime to 2 and 5. But 
is also stubborn, hence all multiples of M must contain all nine nonzero digits. By Euler's Totient Theorem, }-1=kM)
, for some integer k. We arrive at a contradiction because by the theorem, kM consists purely of the digit 9. Hence there exist no stubborn numbers.
Suppose N is stubborn. Then