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.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top