Why not Fermat's Little Theorem?


  • 0
    G

    I applied Fermat's Little Theorem to the Super Pow calculation but doesn't work. According to the theorem, 2^1336 = 1 (mod 1337), but the given answer doesn't match. Why?


  • 0
    A

    Because Fermat's theorem requires that 1337 be a prime number. Which it is not.


  • 1
    E

    Because 1337 = 7 * 191, not a prime, similar formula like fermat's little theorem according to group theorem will be then a^ord(1337) = 1 (mod 1337). For primes p and q: ord(pq) = (p-1)(q-1)
    So here we have a^1140 = 1 (mod 1337)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.