All-9s multiples

[Gengulphus]

As is well-known, any non-negative integer that is divisible by 2 ends with 0, 2, 4, 6 or 8 (when expressed in decimal), and so do all of its multiples. And similarly, any non-negative integer that is divisible by 5 ends with 0 or 5, and so do all of its multiples. So non-negative integers that are divisible by 2 or 5 cannot have any all-9s multiples.

What about non-negative integers that are not divisible by 2 or 5 - do they all have some all-9s multiple, or are there some that don't? For example, 999999 is a multiple of 7, so 7 does have an all-9s multiple.

No credit for just giving the answer - you need to say why it's the answer!

Gengulphus

[UncleEbenezer]

Am I allowed a "social" answer? If the answer is No then a single counterexample will suffice, and (in an era when a program to test for that is a five-minute hack) it's far too boring for you to have posted it.

This is a property of counting in decimal. What's special about 2 and 5 is that they are factors of the number we write as 10.

So the problem is, given a number N such that N is divisible by neither 2 nor 5, is there an M and K such that N*M + 1 = 10^K, all being positive integers?

To find that number, look at 1/N. Since that's a rational number, it can be expressed as a recurring decimal sequence S of length not more than N-1. Taking M as the first N-1 digits of S does the job. Divide 10^N by N and you get M + 1/N, because the sequence S recurs.

Of course, sometimes the recurring sequence is shorter, and we can use that.

[Gengulphus]

Am I allowed a "social" answer? If the answer is No then a single counterexample will suffice, and (in an era when a program to test for that is a five-minute hack) it's far too boring for you to have posted it.

Nice try... ;-) But what if the counterexample is too big for a 'brute search' program to reach it in any reasonable length of time, so that some ingenuity is required to construct it?

So the problem is, given a number N such that N is divisible by neither 2 nor 5, is there an M and K such that N*M + 1 = 10^K, all being positive integers?

To find that number, look at 1/N. Since that's a rational number, it can be expressed as a recurring decimal sequence S of length not more than N-1. ...

No - for instance, the rational number 1/6 is 0.1666..., which is not a recurring decimal sequence, but rather a single digit 1 followed by such a sequence. Of course, 6 is divisible by 2, so that doesn't give a counterexample - but it does mean that there is a problem in your argument.

Or another way of looking at it is that you haven't actually used the fact that N is neither divisible by 2 nor 5 in your argument - so if your argument is valid, then it holds for all non-negative integers. But we know it cannot hold for N divisible by 2 or 5.

Gengulphus

[UncleEbenezer]

No - for instance, the rational number 1/6 is 0.1666..., which is not a recurring decimal sequence, but rather a single digit 1 followed by such a sequence. Of course, 6 is divisible by 2, so that doesn't give a counterexample - but it does mean that there is a problem in your argument.

OK, to be pedantic, my observation should have said a rational number having no common factor between numerator and denominator, including when multiplied by (a power of) the counting base. Dammit, the terminology totally eludes me: my teenage self would've been far more with-it.

Your observation becomes even more obvious when the repeating digit is a zero

[psychodom]

Fermat-Euler theorem (generalisation of Fermat's Little Theorem) states that for coprime n and a positive integers

a^phi(n) = 1 (mod n)

where phi(n) is the Euler Totient Function, which count the positive integers up to integer n that are relatively prime to n.
e.g phi(6) = 2 {4,5}
phi(8) = 4 {3,5,6,7}

this is equivalent to saying
n divides a^phi(n) - 1

Now, let n be not divisible by 2 or 5 and let a = 10
(ie a and n are relatively prime), then

10^phi(n) = 1 (mod n)

which is equivalent to saying, if n is not divisible by 2 or 5 then the number consisting of phi(n) 9's is divisible by n, as required.
(this is not a minimal solution, but that wasn't part of Gengulphus' requirements )

-Dom

[Gengulphus]

Sorry I've been rather slow responding...

OK, to be pedantic, my observation should have said a rational number having no common factor between numerator and denominator, including when multiplied by (a power of) the counting base. Dammit, the terminology totally eludes me: my teenage self would've been far more with-it.

Your observation becomes even more obvious when the repeating digit is a zero

I think you're right - but your corrected observation is not exactly obvious! I.e. I'd say you're stating an equivalent result to the one you're trying to prove, with a proof of the equivalence but not a proof of either result.

Gengulphus

[Gengulphus]

Fermat-Euler theorem (generalisation of Fermat's Little Theorem) states that ...

Same comment...

(this is not a minimal solution, but that wasn't part of Gengulphus' requirements )

Fair comment - but equally, I think it's implicit in posting stuff to this board that it's meant to be treated as a puzzle... (*) It is solvable using elementary ideas of how divisibility and prime numbers behave, without quoting named theorems from number theory, and the solution is not especially long. It's that sort of solution that I'm after.

(*) Assuming it's not a game or riddle instead, of course!

Gengulphus

[jfgw]

Start with 1 followed by a zero. Add more zeroes as you go as required. Divide this number by your chosen divisor (let's call it x) using long division. Since 10^n and x have no common factors (in accordance with the original question), the remainder will cycle through a number of values indefinitely. (By considering the process of long division, it is easy to see why the cycle repeats.)

Examples:

x = 13
Remainders are 9, 12, 3, 4, 1... (repeated indefinitely)

x = 7
Remainders are 3, 2, 6, 4, 5, 1... (repeated indefinitely)

x = 9
Remainders are 1, 1, 1... (repeated indefinitely)

Since the cycle started with a 1 (followed by a number of zeroes), the cycle will always include a remainder of 1.*

If dividing 10^n by x gives a remainder of 1, 10^n-1 must be a multiple of x (and 10^n-1 gives a number consisting of n nines).

In the examples above,

1000000/13 gives a remainder of 1 so 999999 must be exactly divisible by 13.
1000000/7 gives a remainder of 1 so 999999 must be exactly divisible by 7.
10/9 gives a remainder of 1 so 9 must be exactly divisible by 9.

*Note that I have not ruled out a remainder of 10, 100, etc. (although I suspect that it could be ruled out with a bit of thought). Consider a cycle which includes a remainder of 10 rather than 1. This would mean that 10^n-10 would be a multiple. Since this would also be a multiple of 10, and since x and 10 have no common factors, this value could be divided by 10 (leaving just the nines) and still be a multiple of x. Likewise for other powers of 10.

Julian F. G W.

[jfgw]

Start with 1 followed by a zero. Add more zeroes as you go as required. Divide this number by your chosen divisor (let's call it x) using long division. Since 10^n and x have no common factors (in accordance with the original question), the remainder will cycle through a number of values indefinitely. (By considering the process of long division, it is easy to see why the cycle repeats.)

Examples:

x = 13
Remainders are 9, 12, 3, 4, 1... (repeated indefinitely)

x = 7
Remainders are 3, 2, 6, 4, 5, 1... (repeated indefinitely)

x = 9
Remainders are 1, 1, 1... (repeated indefinitely)

Since the cycle started with a 1 (followed by a number of zeroes), the cycle will always include a remainder of 1.*

If dividing 10^n by x gives a remainder of 1, 10^n-1 must be a multiple of x (and 10^n-1 gives a number consisting of n nines).

In the examples above,

1000000/13 gives a remainder of 1 so 999999 must be exactly divisible by 13.
1000000/7 gives a remainder of 1 so 999999 must be exactly divisible by 7.
10/9 gives a remainder of 1 so 9 must be exactly divisible by 9.

*Note that I have not ruled out a remainder of 10, 100, etc. (although I suspect that it could be ruled out with a bit of thought). Consider a cycle which includes a remainder of 10 rather than 1. This would mean that 10^n-10 would be a multiple. Since this would also be a multiple of 10, and since x and 10 have no common factors, this value could be divided by 10 (leaving just the nines) and still be a multiple of x. Likewise for other powers of 10.

Julian F. G W.

[Gengulphus]

*Note that I have not ruled out a remainder of 10, 100, etc. (although I suspect that it could be ruled out with a bit of thought). Consider a cycle which includes a remainder of 10 rather than 1. This would mean that 10^n-10 would be a multiple. Since this would also be a multiple of 10, and since x and 10 have no common factors, this value could be divided by 10 (leaving just the nines) and still be a multiple of x. Likewise for other powers of 10.

Yes, you've basically got the elementary-facts-about-divisibility-and-primes solution I had in mind (there might well be others, of course!). To express it more succinctly:

* Any positive integer N has a multiple of the form (sequence of 9s)(sequence of 0s). Proof: consider the remainders of the sequence of all-9s integers 9, 99, 999, 9999, ... when divided by N. One must be able to find two that are identical by the time one gets to the (N+1)th remainder, since there are only N possible remainders from a division by N. The difference of the two corresponding all-9s integers must be a multiple of N, and it is of the form (sequence of 9s)(sequence of 0s).

* So we have N * M = (sequence of 9s)(sequence of 0s). So if the sequence of 0s is of non-zero length, the primes 2 and 5 both divide N * M, and so each must divide at least one of N and M. So if neither 2 nor 5 divides N, they must both divide M, i.e. M must be a multiple of 10. In which case we can replace M by M' = M/10, and get N * M' = (same sequence of 9s)(sequence of one fewer 0s). Repeat until the sequence of 0s is of zero length, to show that the sequence of 9s without any following 0s is a multiple of N.

Gengulphus