Why not Fermat's Little Theorem?

  • 0

    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

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

  • 1

    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.