BranchesHistoryHelpLogin
Welcome guest
You're not logged in.
261 users online, thereof 0 logged in

The following proposition provides a basis for testing if an integer is a prime number. By contraposition to the corollary, if $a^{p-1}(p)\not\equiv 1(p)$ for some integer $a$ with $p\not\mid a,$ then $p$ is not a prime number. It, therefore, suffices to find any number $a$ with $p\not\mid a$ to prove that $p$ is not prime. On the other hand, to prove that $p$ is prime, we need to show that $a^{p}(p)\equiv 1(p)$ for all integers $a$ with $1 < a < p.$ Therefore, this kind of prooving the primality of $p$ is not efficient, if $p$ is big. Later, we will learn about more efficient proofs of primality than this one.

Proposition: A Necessary Condition for an Integer to be Prime

For any integer $a\in\mathbb Z$ and any prime number $p$ the following congruence holds:

$$a^p\equiv a(p).$$

If $p\not\mid a$ ($p$ does not divide $a$) then $$a^{p-1}(p)\equiv 1(p).$$

| | | | | created: 2019-05-11 18:58:50 | modified: 2019-05-12 09:17:14 | by: bookofproofs | references: [1272]

1.Proof: (related to "A Necessary Condition for an Integer to be Prime")

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[1272] Landau, Edmund: “Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927