Consider the statement “If 
3 divides 
(x^2 + 1), then 3 does not divide 
x.” Consider the following three potential proofs:
1. Assume 3 divides 
x. Then 
x = 3k for some integer 
k. Hence 
x^2 + 1 = (3k)^2 + 1 = 9k^2 + 1 =3(3k^2) + 1 is not divisible by 3.
2. Assume 3 divides (x^2 + 1). So we can write 
x^2 + 1 = 3k for some integer k.Solving for x, we find 
x= \sqrt{3k-1}, which is not divisible by 3.
3. Assume 3 is not divisible by x. So we can write 
x = 3k + 1 or 
3k + 2 for some integer k.In the first case, 
x^2 + 1 = (3k + 1)^2 + 1 = 9k^2 + 6k + 2 = 3(3k^2 + 2k) + 2 is not divisible by 3.In the second case, 
x^2 + 1 = (3k + 2)^2 + 1 = 9k^2 + 12k + 5 = 3(3k^2 + 4k + 1) + 2is also not divisible by 3. So in both cases, 
x^2 + 1 is not divisible by 3.
Which of the three proofs is correct?
