Find the remainder (2^122 + 39)/(2^61 + 2^31 +1)
Вставка
- Опубліковано 22 чер 2024
- Modified 2020 AMC 10B Problem 22 thanks leo.euler AoPS(Art of Problem Solving founded by Richard Rusczyk) for clever modular arithmetic approach. Physics Major Murshed SK related modular arithmetic to Quantum Computing as did mathematician Michael Loceff around 8 years ago. Adherents of Islam are keenly aware of the importance of balancing real world pursuits such as advanced math and spiritual growth/faith.
I tried to solve this by long division, as though it was algebraic long division, and it works. The denominator goes into the numerator 2^61 - 2^31 + 2 - 1 with a remainder of 38.
That was my original attempt, but then I realized modular arithmetic was essentially “one step”.
How many iterations was your long division?
If you have time, will you show your work?
@@MyOneFiftiethOfADollar Four iterations. On the final step, all the powers of 2 cancel, leaving 37 minus -1.
I tried that way and messed up about half way through it. I'm not very neat when writing and was too lazy to track my error. Will try the long division again in the airport next time I get that inevitable late flight.
Perhaps a silly way to do it, lol, but write them out in binary...you get 2^122 + 32 + 7=2^122 + 2^5 + 2^2 + 2 + 1, which, in binary is 100...000100111 for the bottom, etc, and the bottom becomes 100...1....01, etc...with that "1"in the middle the 32nd digit from the right...and just do long division, lol...long division in binary...I keep getting mixed up, lol, but it should give the answer...just be mindful of the missing digits, one can't write them all out...maybe there's a much easier way, lol...I tried just guessing that the largest multiple smaller than the numerator (of the denominator) would be 2^60+2^59...+ 2^2 + 2^1 + 2^0, etc, all 1's in binary...you would multiply that by the denominator and then just subtract, I went back to binary thinking that was even more cumbersome, lol...
I coded in assembly language long ago and have reverent respect for binary and hexadecimal. Love the thought of reducing any problem down to the most rudimentary number system known to man.
I think they inscribed binary on an unmanned spacecraft believing binary to be the most “universal” way to count if other forms of life happened upon the craft!
Ah, interesting...yeah, lol, perhaps it would universal...aliens might, even if not recognizing 0 and 1, guess the two symbols might represent binary, lol, even if perhaps not in the direction (our horizontal right lower to left higher) they might use...
My understanding of why the scientists chose 0,1 is that the notion of night and day on earth might be the closest thing to something “universal “ given that about everything in the universe revolves around a source of light, but one could argue that light is just a waveform in the electromagnetic spectrum that helps humans see. Other forms of life might not depend on it the way we do 😂
I suppose so, lol...yeah, interesting...but I was talking about the symbols themselves, 1, 0, etc...they are not even universal to all humans, or at least were not...2000 years ago the Romans were using different symbols (I guess they didn't have one for 0, but still, lol)...so, what I mean is that aliens are very unlikely to be using the same symbols we use, etc...
@@archangecamilien1879 understood, but the usage of only two symbols irrespective of their appearance may be what is important in conveying on/off, is/ain’t, night/day, absence/presence, true/false blah blah.
Even though, it’s highly improbable that strings of binary digits would mean anything to other life forms AND we haven’t even broached what it means to be alive 😂
The result is indeed 38, and to prove it all you need to do is show that 2^122 + 1 is a multiple of 2^61 + 2^31 + 1. A quick way to do it is observe that (x^61 + x^31 + 1)(x^61 - x^31 + 1) = x^122 - x^62 + 2 x^61 + 1, then replace x with 2 and get (2^61 + 2^31 + 1)(2^61 - 2^31 + 1) = 2^122 + 1, voilà!
Quick? I noticed you had to edit your solution .
How would you know to use your method without first knowing the remainder was 38?
@@MyOneFiftiethOfADollar The edit was minor (adding a space after a minus sign for esthetics). On the other hand my comment is not intended as a full solution from scratch, it is just a shortcut for an already known solution. I think the factorization trick has its own interest.
@@mlerma54 I certainly think your approach is flawless for different instructions, namely “prove the remainder for this quotient is 38”.
However, the problem in video is “Find the Remainder”
Will try to compose a problem that uses your, what I would call, verification technique.
Thx for your interest and the approach you shared.