Modular Arithmetic/Sophie Germain's Theorem

From Wikibooks, open books for an open world
Jump to navigation Jump to search
Sophie Germain’s Theorem

Let be a prime number. Then, for the equation,

it is true that at least one of the numbers must be divisible by , if and only if there exists a prime , such that:

  1. No two nonzero powers differ by one modulo ;
  2. is itself not a power modulo .

Corollary: The first case of Fermat's Last Theorem (the case in which does not divide ) must hold for every prime if there exists a prime for which (1) and (2) hold.