**Review (Screener)**

Problem:

Shows that 121 does not divide f (n) = n ^ 2 + 3n +5 for any natural number n.

Review:

Title: R_121_Criba In the petition "shows that 121 does not divide n ^ 2 + 3n + 5 for any natural n" the first thing that strikes our mind is the negative of the proposition (not divided) . How can I handle this? Ie how do you handle a negative proposition? If you ask "Prove that 121 divides a. .." like that somehow feels more manageable problem. But as it is posed the problem seems to us not computable, not processed by our cognitive systems. But it is. The force method Gross is daunting test for 1, 2, 3, ... A never ending story. "Induction? But if it is a denial? And our mind begins to spin in a whirlwind. But cool! If proposed in a contest should be resolvable. Moreover, it should be easy. First you have to look for clues of where you can enter. For any problem of competition must have a point of attack, a point where we can start thinking about your solution. The first clue lies in understanding what is asked. To avoid negative reading Let's think like I ask you to show that something is impossible (the 121 divide f (n)). If you know how to handle cases congruences reduce to 120 and you can apply brute force. And if well-organized calculations can verify the 120 cases in half an hour. But there's another track: 121 = 11 ^ 2. Why is it a clue? Well, because 11 is prime, and to verify that it is impossible that 121 divides f (n) is enough to prove that 11 does not divide twice to no n. The proposition calls for show can be translated as follows: two times 11 does not divide f (n). And here is now the key to the show: to divide into cases. (The 11 does not divide f (n), and if once divided not divide a second time.) Is the happy idea. The screening method. Another way to translate the problem and leads to the screen is to show that C = {n / 121 divides f (n)} is an empty set. The idea of \u200b\u200bscreening is to reduce on the search space. In principle, all cases must be analyzed. But with the screen first searched the n for which 11 divides f (n). This reduces the search space. Then in the set B = {n / 11 divided af}, we verify if 121 divides f for some element of B. First screen (method to determine if 11 divides f (n) for some n) as f (n) = n ^ 2 + 3n + 5 is not factorizable, it is factored leaving a multiple of 11 independent term. This requires adding and subtracting a constant c such that c + 5 is a multiple of 11 but at the same time, certain factors-c, say, c = ab, would have added the coefficient n in the equation, a + b = 3. (These formulas Vieta, a factorization method is applied intuitively and by trial and error: with practice the method considerably easier.) For this case we have (after several attempts): n ^ 2 + 3n +5 +28 - 28. The transformation sought, since n ^ 2 +3 n - 28 +33 meets the requirements and results in the factorization f (n) = (n + 7) (n - 4) + 33. And you can see that f is a multiple of 11 if and only if n = 4 + multiple of 11 (say n = 4 + 11k, with k an integer). Thus B = {n / n = 4 + 11k, k integer}. Second sieve The second sieve acts only on elements of B. For this is substituted into f (n) the generic element of B: f (4 + 11k) = (4 + 11k +7) (4 +11 k - 4) + 33 = 11 (k +1) +33 = 121k 11k (k + 1) +33.} And you can see that 121 will never divide f. Demonstrate general problem that does not divide p ^ 2 f (n) = n ^ 2 + (a + b) n + d for any natural n (p a prime). First we seek a constant c such that c + d = kp and at the same time-c = ab. The function would be f (n) = n ^ 2 + (a + b) n + ab + kp = (n + a) (n + b) + kp. Hence p divides f if and only if n = - a + rp or when n = - b + sp, with r and s integers. (Yes - a + b = p the problem is simplified and therefore only have to prove for-a + rp.) In the second screen would have: (-a + rp + a) (-a + rp + b) + kp = rp (r + 1) p + kp = r (r + 1) p ^ 2 + kp. Generating a problem Let p = 7, a = 2, b = -5, d = 4. Then the problem would be: to demonstrate that 49 does not divide n ^ 2 - 3n +4. Adding and subtracting 10 gives: n ^ 2 - 3n + 4 + 10 - 10 = n ^ 2 - 3n - 10 + 14 = (n + 2) (n - 5) + 14. So 7 divides f (n) if and only if n = -2 +7 k. But these numbers have f (-2 + 7k) = 49k (k + 1) + 14. And you can see that 49 does not divide f (n) for any n. Tip

Review