Petit théorème de Fermat

• Soit p premier et a non multiple de p,
  
  
• Les p-1 premiers multiples de a : a, 2a, …, (p-1)a sont tous distincts et non nuls modulo p.
  
  
• En effet si na=ma mod p alors n=m mod p (car p ne divise pas a). D’autre part si p divisait ka (1<k<p-1) il diviserait a
  
  
• Ces p-1 entiers valent donc 1, 2, ... , p-1 dans un certain ordre.
  
  
• Par multiplication, on obtient a^p-1(p-1)! = (p-1)! mod p
  
  
• Par simplification par (p-1)! on obtient:
  
          a^p-1 mod p = 1