MHB Find Remainder When Divided by 19

  • Thread starter Thread starter Deanmark
  • Start date Start date
  • Tags Tags
    Remainder
AI Thread Summary
To find the remainder of 2^(2^17) + 1 when divided by 19, it is necessary to first compute 2^17 mod 18 due to Fermat's Little Theorem, which states that a^(p-1) mod p equals 1 for a prime p. By expressing 2^17 as a multiple of 18 plus a remainder, the calculation simplifies to 2^(18k + r) mod 19, which can be reduced to 2^r + 1 mod 19. This approach allows for easier computation of the original expression. Understanding this method clarifies the reasoning behind using mod 18 before applying mod 19.
Deanmark
Messages
16
Reaction score
0
Compute the remainder of 2^(2^17) + 1 when divided by 19. The book says to first compute 2^17 mod 18 but I don’t understand why we go to mod 18. Advice would be appreciated
 
Mathematics news on Phys.org
Deanmark said:
Compute the remainder of 2^(2^17) + 1 when divided by 19. The book says to first compute 2^17 mod 18 but I don’t understand why we go to mod 18. Advice would be appreciated

Hi Deanmark,

That's because of the Little Theorem of Fermat:
$$a^{p-1} \bmod p = 1$$
where $p$ is prime and $a$ is any number except for a multiple of $p$.

So if we can write $2^{17}$ as some multiple of $18$ and a remainder, say $2^{17} = 18k + r$, then:
$$2^{(2^{17})} + 1 \bmod 19 = 2^{18k+r} + 1 \bmod 19 = (2^{18})^k\cdot 2^r + 1 \bmod 19 = 2^r + 1 \bmod 19$$
 
The parts of my wall that have yet to be punched thank you.
 
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