Proof 3: Logical Reasoning and Proofs: Encryption and Security

Network security and encryption are also a concern of IT personnel. Many encryption schemes are based on number theory and prime numbers, for example, RSA encryption. These methods rely on the difficulty of computing and testing large prime numbers. (A prime number is a number that has no divisor except for itself and 1.)

For example, in RSA, one must choose two prime numbers,p,andq; these numbers are private, but their product,z=pq,is public. For this scheme to work, it is important that one cannot easily findporqgivenz, sopandqare generally large numbers. Seemingly, this strategy would work best if many large prime numbers are not easy to guess the prime divisor of z.

Prove or disprove the following statement: There are infinitely many prime numbers.Hint:Use the fact that all integers greater than 1 can be represented as a product of primes.

1. State yourproof idea. What type of proof will you use to prove or disprove this inequality, and why?
2. Prove or disprove the statement.