MathDB
2015 Algebra #8: Double Quadratic Residues

Source:

March 28, 2015
quadraticsabstract algebraalgebrapolynomial

Problem Statement

Find the number of ordered pairs of integers (a,b)∈{1,2,…,35}2(a,b)\in\{1,2,\ldots,35\}^2 (not necessarily distinct) such that ax+bax+b is a "quadratic residue modulo x2+1x^2+1 and 3535", i.e. there exists a polynomial f(x)f(x) with integer coefficients such that either of the following <spanclass=′latex−italic′>equivalent</span><span class='latex-italic'>equivalent</span> conditions holds:
[*] there exist polynomials PP, QQ with integer coefficients such that f(x)2−(ax+b)=(x2+1)P(x)+35Q(x)f(x)^2-(ax+b)=(x^2+1)P(x)+35Q(x); [*] or more conceptually, the remainder when (the polynomial) f(x)2−(ax+b)f(x)^2-(ax+b) is divided by (the polynomial) x2+1x^2+1 is a polynomial with integer coefficients all divisible by 3535.
Back to ProblemsView on AoPS