Proof 1: Logical Reasoning and Proofs: Application Server Load

Assume you have been tasked with assessing the "load" or "user traffic" that users might impose on your company's servers. Specifically, you wish to bound the total number of threads opened up on the servers given the number of users active. Given initial analysis, the number of threads, t, can be estimated in terms of the number of users, n, within a reasonable error using the following equation:

ⁿ_x= 1^x = (1 + 2 + 3 + + n) = t

You believe n² is a reasonable bound for (1 + 2 + 3 ++ n). To justify this, you must first prove the following inequality holds for all integers n 1.

(1 + 2 + 3+ + n) = n²

1. State your proof idea. What type of proof will you use to prove/disprove this inequality and why?

2. Prove or disprove the inequality.

Proof 2: Logical Reasoning and Proofs: Functions and Discrete Structures

Security and encryption is also a concern of IT personnel. Many simple encryption schemes rely on the use of the modulus function. The modulus function is also popularly used as a hash function, which is used in the construction of hash tables. The modulus function returns the remainder value resulting from a division operation. For example, 6 mod 5 = 1 and 13 mod 7 = 6.

3. In order to build an appropriate hash function, one must have a good understanding of the properties of the hash function used. To this end, prove or disprove the following statement for all positive integers n and m. 2 ⁿ mod 2 m = 4 ⁿ mod 2( m+ 1)

Proof 3: Logical Reasoning and Proofs: Encryption and Security

Network security and encryption is 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 and q; these numbers are private but their product, z = pq is public. For this scheme to work, it is important that one cannot easily find p or q given z, which is why p and q are generally large numbers. Seemingly this strategy would work best if there are many large prime numbers, so that one could not easily 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.

4. State your proof idea. What type of proof will you use to prove or disprove this inequality and why?

5. Prove or disprove the statement.