How do you know there is a factor of 101 still hidden in there
-
In Prof. Loh's explanation for the question he said to take out the 101, but how can you see that there is such a large prime hidden in there? Do you check every single prime?
One day you will realize...
-
@perceptiveeagle I don't know, but I think because multiples of 101 can be written as 100x+x, it's somewhat easier to recognise.
-
@perceptiveeagle You're right-- it's pretty difficult to see a factor of 101 in 910010 and 100091.
@RZ923 has a great tip, thinking of 101 as (100+1) is usually a great step towards finding an easier solution, but here it doesn't make it much easier. Usually though, if you ever see numbers like \(3434, 9191, 2828\), those are giveaways for 101.If you do end up using the idea of \((100+1)\), you might be able to experiment with a few numbers and notice that it has to be 9010 and 991. Since \((100+1)\cdot x = (100x+x)\) , the only things contributing to the units digit and tens digit are the last two digits of the number itself, since \(100x\) will only contribute to values from the hundreds digit and beyond. So, we know that if the two numbers were to be divisible by 101, they would need to end with \(10\) and \(91\). This gives you a great start, and using the same idea with the first two digits, since what would contribute the most to the hundred thousands are the first few digits of the number. We could try \(9110\) and \(1091\), but that overshoots it. Using that, we can deduce that the numbers are \(9010\) and \(991\).
Buuut, to be honest, that isn't too intuitive either. So, let's use an idea that we're familiar with!
A review of the divisibility rule of 11 that I'm sure you've seen many times: to check if a number is divisible by 11, alternate adding and subtracting its digits and the result you get is the remainder of the original number divided by 11.For example, \(12342 \implies 1-2+3-4+2 = 0 \) this number is divisible by 11!
\(11=10^1+1\). This fact is very useful in proving why the method works. Can you give it a shot?
Because, using the same idea, we can check divisibility by 101!
Instead of alternating digits, we're going to pair up digits and then alternate, starting from the right.For example, \(91304 \implies 9 -13 +04 = 0\) this number is divisible by 101!
Note: 9 is by itself here since we started pairing from the right.So in \(910010\), we pair up every two digits starting from the right: \(91, 00, 10\). Then, alternating adding and subtracting: \(91-00+10=101\), so since the number leaves a remainder of 101 when divided by 101, that's the same as leaving remainder 0, so the number is divisible by 101!
Same with \(100091\):\(\text{ } 10-00+91 =101\) divisible by 101!
\(101=10^2+1\), which is very useful in proving why this works. Again, do you think you could give it a shot?
Also, do you see a pattern yet? \(1001=10^3+1\). So would these numbers be divisible by \(1001?\)
\(7004998,4009005,740824084\) -
@quacker88 thanks for your reply! I tend to use negative remainders when I prove divisibility by 101. So:
\(ABCDEF = AB \times 10000 + CD \times 100 + EF (mod 101) \)
\(ABCDEF = AB(-1)^2+ BC(-1)+DE (mod 101)\)
\(ABCDEF=AB-BC+DE (mod 101)\)This creates an alternating pattern. However, I'm not exactly too sure about how to use \(10^2+1\) to prove. Is it just grouping by twos because of the \(10^2?\) Can you please show me how to do it?
(sorry I'm bad at typing latex) -
@perceptiveeagle You did it perfectly! My hint may have been a bit misleading, what I was trying to get to is the fact that \(100 \equiv -1 \pmod{101}\), which is exactly what you did.
Also, this trick for 101 is essentially the same thing as converting the number into a base 100 number and then alternating the digits, as we do for 11 in base 10! I think it's pretty cool.
Oh, and don't worry about your LaTeX! I can perfectly understand it. Although here's a trick for writing mods if you want to in the future:
The congruence symbol is \equiv, and the mod symbol is \pmod{a}. So,
3 \equiv 1 \pmod{2} gives me \(3\equiv 1 \pmod{2}\).
Great work!
-
@quacker88 Ok thank you I got that
