MHB Find Remainder of $2^{100}-1$ Divided by 1000

  • Thread starter Thread starter Amad27
  • Start date Start date
AI Thread Summary
The discussion focuses on finding the remainder of \(2^{100} - 1\) when divided by 1000. It establishes that \(2^{100} \equiv 1 \pmod{125}\) and \(2^{100} \equiv 0 \pmod{8}\), leading to the conclusion that \(2^{100} \equiv 376 \pmod{1000}\). The sum of all possible remainders when powers of 2 are divided by 1000 is considered, with the importance of including additional powers like \(2^{101}\) and \(2^{102}\) noted. The discussion also touches on generalizing the findings to higher powers of 10. Ultimately, the conversation emphasizes the cyclical nature of powers of 2 in modular arithmetic.
Amad27
Messages
409
Reaction score
1
>Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of all elements in $R$. Find the remainder when $S$ is divided by $1000$.

Here is my working:$2^{\phi(x)} \equiv 1 \pmod{x}$ such that $(2, x) = 1$. So let $x = 125$.

$2^{100} \equiv 1 \pmod{125}$ and consider the cycle that:

$2^{100k + n} \equiv 2^n \pmod{125}$.

$\forall n \ge 3 \implies 2^n \equiv 0 \pmod{8}$.

So I got:

$S = \sum_{k=1}^{99} 2^k = 2^{100} - 1$ but the real answer also considers $2^{100, 101, 102}$ why? $2^{100} \equiv 1 \pmod{125}, 2^{100} \equiv 0 \pmod{8} \implies 2^{100} \equiv 376 \pmod{1000}$.

And then why do they just stop at $102$, what about $103$ etc??
 
Mathematics news on Phys.org
Hi,
As mathematicians love to do, I generalized your statement to any power of 10 greater than 0. I hope the following answers your questions; in particular the text in red shows why the set of remainders is exactly what you wondered about.

View attachment 4587
View attachment 4588
 

Attachments

  • johng003.png
    johng003.png
    14.6 KB · Views: 100
  • johng004.png
    johng004.png
    5.4 KB · Views: 105
Last edited by a moderator:
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top