andrei 0 Report post Posted February 12, 2017 A palindrome is a number which reads the same backward or forward (e.g. 434, 87678, etc.). Could you prove that for any integer n (not divisible by 10) there is a palindrome divisible by n? *** I've checked for all numbers up to 162, it's true: 81* 12345679= 999999999 172839506*162=27999999972 Is there any simple proof for any integer? Quote Share this post Link to post Share on other sites
1 ronald 0 Report post Posted June 28, 2017 Yes, this can be proven. The proof is relatively simple but it does require knowledge of Euler's theorem and Euler's totient function (See https://en.wikipedia.org/wiki/Euler's_theorem) The proof consists of 3 steps and constructs an explicit palindrome for every number n that is not divisible by 10. This will be a possible solution, but by no means the smallest palindrome divisible by n. In fact the constructed palindrome get very large. 1) Find a solution for n=2^{k} or n=5^{k} for every integer k=1,2,3,.... Spoiler We need a function r(n) that reverses the order of digits of the number n. Since we only allow numbers that are not divisible by 10 we can ignore the problem of zero's at the begin or end of a number and what it implies for the function r(n) Example: r(12345) = 54321 The number: r(2^{k})*10^{k}+2^{k} = r(2^{k})*2^{k}*5^{k}+2^{k} = {r(2^{k})*5^{k}+1}2^{k} is divisible by 2^{k} and is also a palindrome for any value of k The number: r(5^{k})*10^{k}+5^{k} = r(5^{k})*2^{k}*5^{k}+5^{k} = {r(5^{k})*2^{k}+1}5^{k} is divisible by 5^{k} and is also a palindrome for any value of k Example: n=2^{6}=64 would give r(64)*10^{6}+ 64 = 46*10000 + 64 = 46000064 This is significantly larger than the smallest palindrome 2112 that is a multiple of 64 We could reduce the solution a little bit by adjusting the power of 10, because for instance 4600064 is also a multiple of 64. Whether this can be done or not depends on the digital representation of the number 2^{k}. If we consider n=2^{5}=32 we get 2300032, but 230032 would not be divisible by 32. 2) Find a solution for any value of n that does not contain a factor 2 or 5 Spoiler Here we need Euler's theorem, which states that for every pair of integers a and n that have no common factor, there is a number f(n) such that a^{f(n)} when divided by n has the remainder 1. If anyone want to know more see the Wikipedia https://en.wikipedia.org/wiki/Euler's_theorem for a proof of the theorem. In order to compute f(n) you need to find all prime factors of the number n (See https://en.wikipedia.org/wiki/Euler's_totient_function). If we use this for the case a=10 and we restrict n to numbers not divisible by 2 and 5 we get that 10^{f(n)}-1 is divisible by n and since this number is written as a sequence of f(n) digits of 9 this is a palindrome as well. Example: for n=7 we would have f(7)=6 and therefore 10^{6}-1=999999 is divisible by 7 So for any number n that is not divisible by 2 or 5 there is a palindrome that is a sequence of f(n) digits of 9 and that is divisible by n. This can be extended, because any multiple of f(n) would also be fine. We also have 10^{12}-1=999999999999, 10^{18}-1=999999999999999999, ... which are also divisible by 7. Note that f(n) is guaranteed to work but is not necessarily the smallest power that is required. For instance for n=21 we get f(21)=12 and 10^{12}-1 is divisible by 21, but so is the number 10^{6}-1. 3) Find a solution for any value of n that does contain a factor 2 or 5 Spoiler The only numbers that are left to do are of the form n=2^{k}*m or n=5^{k}*m, where m does not contain a factor 2 or 5. For this we need to construct a palindrome that combines both of the previous solutions with a small variation. It can generally be proven, but I will sketch here just the strategy to construct a possible solution for the palindrome by using the example of n=5^{k}*7. For m=7 we have f(7)=6 and hence 10^{6} has a remainder 1 when divided by 7. The same is true for 10^{12}, 10^{18},10^{24},.... So a different (much bigger) palindrome that we could have constructed would have been the sum of m=7 such terms that each would have a remainder 1 and hence their sum would be divisible by 7 as well. 1 + 10^{6} + 10^{12 }+ 10^{18}+ 10^{24 }+ 10^{30}+ 10^{36} = 1000001000001000001000001000001000001 If we now have a palindrome that is a multiple of 5^{k }and multiply it with the one above we get exactly what we want, because multiplying a short palindrome with a palindrome of the type above is again a palindrome. k=1 gives a pre-factor 5 and has the palindrome 55 with the method above (of course 5 is already a palindrome and would also work), multiplying we get 55000055000055000055000055000055000055. k 5^{k} palindrome 1 5 55 55000055000055000055000055000055000055 2 25 5225 5225005225005225005225005225005225005225 3 125 521125 521125521125521125521125521125521125521125 This works as long as the palindrome that is a multiple of m is shorter than 10^{f(m)}. For larger values of k we just need to increase the gaps in between the digits 1, which is easy enough because we could also have used: 1 + 10^{12} + 10^{24 }+ 10^{36}+ 10^{48 }+ 10^{60}+ 10^{72} = 1000000000001000000000001000000000001000000000001000000000001000000000001 or 1 + 10^{18} + 10^{36 }+ 10^{54}+ 10^{72 }+ 10^{9}^{0}+ 10^{108} = ...... 1 + 10^{24} + 10^{48 }+ 10^{72}+ 10^{96 }+ 10^{12}^{0}+ 10^{144} = ...... and make the gap of digits 0 as large as we would like. Since the final palindrome we obtain is formed by multiplying a short palindrome that is a multiple of 5^{k} and a long palindrome that is a multiple of m the resulting palindrome is divisible by n. The same approach work for al numbers of the form n=2^{k}*m or n=5^{k}*m, they just tend to get very large in this particular construction. PS. If one would allow for zero's at the beginning of a digit representation of a number it can be extended to any number n. Quote Share this post Link to post Share on other sites
0 Alkis 0 Report post Posted March 6, 2017 (edited) On 12/2/2017 at 8:14 PM, andrei said: A palindrome is a number which reads the same backward or forward (e.g. 434, 87678, etc.). Could you prove that for any integer n (not divisible by 10) there is a palindrome divisible by n? *** I've checked for all numbers up to 162, it's true: 81* 12345679= 999999999 172839506*162=27999999972 Is there any simple proof for any integer? Indeed, 81 is the first number that requires a long divisor its palindrome is very long. I didn't have the patience to go up to nine digits, as you did. I stopped when the quest for a palindrome reached 8 digits (It took alreadt 32 secs!). In a PC I checked all numbers 1-1000 and, here are the numbers with >=8-digit result (not sulution!): 81, 162, 243, 324, 405, 486, 567, 648, 655, 729, 891, 972. There are no many and may there is a reason for that. For one thing they are multiples of 81, with 1-11 as multipliers ... So, it happens that 81 is the "mystery" number! Now, it seems there's indeed a palindrome for every number. But how indeed can it be prooven (if it can)? On 12/2/2017 at 8:14 PM, andrei said: (My comment has been posted twice - See previous one Edited March 6, 2017 by Alkis It has been posted twice! Quote Share this post Link to post Share on other sites
A palindrome is a number which reads the same backward or forward (e.g. 434, 87678, etc.). Could you prove that for any integer n (not divisible by 10) there is a palindrome divisible by n?
***
I've checked for all numbers up to 162, it's true:
81* 12345679= 999999999
172839506*162=27999999972
Is there any simple proof for any integer?
Share this post
Link to post
Share on other sites