Consider a number, n. We wish to find some multiple M(n) of n we can write with 0s and 1s.
Lets look at n which is not a multiple of 2 or 5. Then for all numbers which are 2^x * 5*y * n (n not a multiple of 2 or 5), we can find the solution for n, and look at 10^max(x,y) * M(n).
OK, now consider 10 modulo n. They are coprime, so by Euler's Theorem (the totient one), 10^phi(n) == 1 (mod n). Call this number T.
Now look at:
T^(n-1) + T^(n-2) + ... T + 1
T is a power of ten (10 or greater), so that is a number like 10001000...10001 which fulfills the condition. And modulo n, it is equal to 1+1+1...1, ie equal to n. Hence is a multiple of n as desired.
Is that right?
If so, I felt there must be a shorter way than having n copied of 10^phi(n), is there?
I don't there to normally be a convenient formula that species a *minimum* multiple, (even though there's a better solution in the comments on LJ than my solution). Am I missing something?
My immediate reaction was "define number": is there a multiple of π that you can write that way, other than the degenerate cases of multiplying by zero or taking to the zeroth power?
In this case, a positive integer. I would usually try to specify "positive integer" (anything involving number theory/expression with digits/multiples is almost always positive integer), but I left it ambiguous so people could post the funny "multiply by 0" answer :)
I remember observing that mathematicians tend to care about everything being defined *somewhere* but they do exactly the same sloppy deduce-from-context as everyone else a lot of the time, expecting it be obvious when "number" means "positive integer" and when it means "real number" and maybe when it means "any ring", or knowing when "function" means "anything from anything" and when it means "a smooth continuous function from R to R".
Yes, and in a lot of contexts I would assume the same: but once something is labeled as a "riddle," "brain teaser," or "puzzle," I start to suspect that the trickiness is in the phrasing of the question.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jack
no subject
Date: 2016-11-14 01:04 pm (UTC)Yes, because you can always multiply by 0 :)
no subject
Date: 2016-11-14 01:16 pm (UTC)Consider a number, n. We wish to find some multiple M(n) of n we can write with 0s and 1s.
Lets look at n which is not a multiple of 2 or 5. Then for all numbers which are 2^x * 5*y * n (n not a multiple of 2 or 5), we can find the solution for n, and look at 10^max(x,y) * M(n).
OK, now consider 10 modulo n. They are coprime, so by Euler's Theorem (the totient one), 10^phi(n) == 1 (mod n). Call this number T.
Now look at:
T^(n-1) + T^(n-2) + ... T + 1
T is a power of ten (10 or greater), so that is a number like 10001000...10001 which fulfills the condition. And modulo n, it is equal to 1+1+1...1, ie equal to n. Hence is a multiple of n as desired.
Is that right?
If so, I felt there must be a shorter way than having n copied of 10^phi(n), is there?
no subject
Date: 2016-11-14 01:59 pm (UTC)no subject
Date: 2016-11-15 11:19 am (UTC)no subject
Date: 2016-11-14 08:01 pm (UTC)no subject
Date: 2016-11-15 11:17 am (UTC)I remember observing that mathematicians tend to care about everything being defined *somewhere* but they do exactly the same sloppy deduce-from-context as everyone else a lot of the time, expecting it be obvious when "number" means "positive integer" and when it means "real number" and maybe when it means "any ring", or knowing when "function" means "anything from anything" and when it means "a smooth continuous function from R to R".
no subject
Date: 2016-11-15 01:02 pm (UTC)no subject
Date: 2016-11-15 02:19 pm (UTC)