Data Structures and Algorithms Using Java

APPENDIX C

Proof That If an Integer, P, Is Not Evenly Divisible by an Integer Less Than the Square Root of P, It Is a Prime Number

Preliminary Proof

Given:

R = the square root of P.

Prove:

If P = H * L, either H = L = the square root of P, or H or L is < R and the other is > R.

Proof:

If both were > R, then their product would be greater then P, and if both were less than R, their product would be less than P.

 

Desired Proof

Given:

There are no integers less than R (the square root of P) that divide evenly into P.

Prove:

There are no integers greater than R that divide evenly into P.

Proof:

Assume:H is an integer > R and that H divides evenly into.

Then: Define Las L = P / H.

L is an integer, since L = P / H and H divides evenly into P