Difference between revisions of "KGS math club/solution 2 1"
(solution to a kgs problem) |
(No difference)
|
Revision as of 21:32, 20 June 2008
Answer: No. Proof: Lemma 1: 2007 = 223 * 3^2 (trivial) Lemma 2: x(n) = 2^n * (n^2 + 1) (letting x(0) = 1, x(1) = 4 and x(2) = 20) Proof: Induction over n. For n = 3: n(3) = 6 * 20 - 12 * 4 + 8 = 80 = 2^3 * (3^2 + 1) For n > 3: assume x(n) = 2^n * (n^2 + 1) and similarly for x(n-1) and x(n-2). then x(n+1) = 6 * 2^n * (n^2 + 1) - 12 / 2 * 2^n * (n^2 - 2n + 2) + 8 / 4 * 2^n * (n^2 - 4n + 5) = 2^n * ( (6 - 6 + 2) n^2 + (-6*-2 + 2*-4) n + (6 - 6*2 + 2*5) ) = 2^n * 2 * (n^2 + 2n + 1 + 1) = 2^(n+1) * ( (n+1)^2 + 1) Thus, formula holds for all n >= 3, q.e.d. Serious business observation: neither 3 nor 223 (both odd) are going to divide 2^n (which is always even) given any n, same applies the other way around. Thus it remains to show that neither 3 not 223 divide n^2+1, the other factor of x(n). That is equailent to showing that For all n, n^2 != 2 (mod 3) and n^2 != 222 (mod 223) or in other words, that 2 and 222 are not quadratic residues modulo 3 and 223 respectively. Using Euler's criterion (for those _really_ interested in the proof, look it up in Wikipedia) we decide: 2^((3-1)/2) = 2^1 = 2 = -1 (mod 3) meaning that 2 is _not_ a quadratic residue modulo 3 and 222^((223-1)/2) = 222^111 = 222 = -1 (mod 223) meaning that, indeed, 222 is not a quadratic residue modulo 223 concluding the proof. Thank YOU for reading this far. Looks like that makes two of us (not having life...) Yours, sigs