{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"omni-math","formal_name":"Omni-MATH","introduction":"Omni-MATH evaluates mathematical reasoning on Olympiad-level problems. Its official dataset contains 4,428 problems accompanied by domain and difficulty information.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://huggingface.co/datasets/KbsdJames/Omni-MATH","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"91ecd8d8-b10a-5539-927d-c38b30a16b93","task_key":"test--91ecd8d8-b10a-5539-927d-c38b30a16b93","task_revision_id":"4","upstream_id":"","short_description":"[color=blue][b]Generalization.[/b] Given two integers $ p$ and $ q$ and a…","config":"","split":"test","body":"{\"problem\":\"[color=blue][b]Generalization.[/b] Given two integers $ p$ and $ q$ and a natural number $ n \\\\geq 3$ such that $ p$ is prime and $ q$ is squarefree, and such that $ p\\\\nmid q$.\\nFind all $ a \\\\in \\\\mathbb{Z}$ such that the polynomial $ f(x) \\\\equal{} x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ can be factored into 2 integral polynomials of degree at least 1.[/color]\\r\\n\\r\\n[i]Solution.[/i] I hope the following solution is correct. It is more or less a straightforward generalization of [url=http://www.kalva.demon.co.uk/imo/isoln/isoln931.html]IMO 1993 problem 1[/url].\\r\\n\\r\\nThe idea behind is an extension of Eisenstein's criterion for irreducible polynomials:\\r\\n\\r\\n[color=blue][b]Lemma 1.[/b] Let p be a prime number. If a polynomial $ A\\\\left(x\\\\right) \\\\equal{} a_nx^n \\\\plus{} a_{n \\\\minus{} 1}x^{n \\\\minus{} 1} \\\\plus{} ... \\\\plus{} a_1x \\\\plus{} a_0$ with integer coefficients $ a_n$, $ a_{n \\\\minus{} 1}$, ..., $ a_1$, $ a_0$ is reducible in $ \\\\mathbb{Z}\\\\left[x\\\\right]$, and the prime p divides the coefficients $ a_0$, $ a_1$, ..., $ a_{n \\\\minus{} 2}$, but does not divide $ a_n$, and $ p^2$ does not divide $ a_0$, then p does not divide $ a_{n \\\\minus{} 1}$, and the polynomial A(x) must have a rational root.[/color]\\r\\n\\r\\n[i]Proof of Lemma 1.[/i] Since the polynomial A(x) is reducible in $ \\\\mathbb{Z}\\\\left[x\\\\right]$, we can write it in the form A(x) = B(x) C(x), where $ B\\\\left(x\\\\right) \\\\equal{} b_ux^u \\\\plus{} ... \\\\plus{} b_1x \\\\plus{} b_0$ and $ C\\\\left(x\\\\right) \\\\equal{} c_vx^v \\\\plus{} ... \\\\plus{} c_1x \\\\plus{} c_0$ are non-constant polynomials with integer coefficients $ b_u$, ..., $ b_1$, $ b_0$, $ c_v$, ..., $ c_1$, $ c_0$. Then, for any i, we have $ a_i \\\\equal{} \\\\sum_{k \\\\equal{} 0}^i b_kc_{i \\\\minus{} k}$ (this follows from multiplying out the equation A(x) = B(x) C(x)). Particularly, $ a_0 \\\\equal{} b_0c_0$. But since the integer $ a_0$ is divisible by the prime p, but not by $ p^2$, this yields that one of the integers $ b_0$ and $ c_0$ is divisible by p, and the other one is not. WLOG assume that $ b_0$ is divisible by p, and $ c_0$ is not.\\r\\n\\r\\nNot all coefficients $ b_u$, ..., $ b_1$, $ b_0$ of the polynomial B(x) can be divisible by p (else, $ a_n \\\\equal{} \\\\sum_{k \\\\equal{} 0}^n b_kc_{n \\\\minus{} k}$ would also be divisible by p, what is excluded). Let $ \\\\lambda$ be the least nonnegative integer such that the coefficient $ b_{\\\\lambda}$ is [i]not[/i] divisible by p. Then, all the integers $ b_k$ with $ k < \\\\lambda$ are divisible by p. Hence, in the sum $ a_{\\\\lambda} \\\\equal{} \\\\sum_{k \\\\equal{} 0}^{\\\\lambda} b_kc_{\\\\lambda \\\\minus{} k}$, all the summands $ b_kc_{\\\\lambda \\\\minus{} k}$ with $ k < \\\\lambda$ are divisible by p, but the summand $ b_{\\\\lambda}c_0$ (this is the summand for $ k \\\\equal{} \\\\lambda$) is not (since $ b_{\\\\lambda}$ is not divisible by p, and neither is $ c_0$). Hence, the whole sum $ a_{\\\\lambda}$ is not divisible by p. But we know that the coefficients $ a_0$, $ a_1$, ..., $ a_{n \\\\minus{} 2}$ are all divisible by p; hence, $ a_{\\\\lambda}$ must be one of the coefficients $ a_{n \\\\minus{} 1}$ and $ a_n$. Thus, either $ \\\\lambda \\\\equal{} n \\\\minus{} 1$ or $ \\\\lambda \\\\equal{} n$.\\r\\n\\r\\nIf $ \\\\lambda \\\\equal{} n$, then it follows, since the integer $ b_{\\\\lambda}$ is defined, that the polynomial B(x) has a coefficient $ b_n$. In other words, the polynomial B(x) has degree n. Since the polynomial A(x) has degree n, too, it follows from A(x) = B(x) C(x) that the polynomial C(x) is a constant. This is a contradiction.\\r\\n\\r\\nThus, we must have $ \\\\lambda \\\\equal{} n \\\\minus{} 1$. Hence, the integer $ a_{n \\\\minus{} 1} \\\\equal{} a_{\\\\lambda}$ is not divisible by p. Also, since the integer $ b_{\\\\lambda}$ is defined, it follows that the polynomial B(x) has a coefficient $ b_{n \\\\minus{} 1}$. In other words, the polynomial B(x) has degree $ \\\\geq n \\\\minus{} 1$. Since the polynomial A(x) has degree n and A(x) = B(x) C(x), this yields that the polynomial C(x) has degree $ \\\\leq 1$. The degree cannot be 0, since the polynomial C(x) is not constant; thus, the degree is 1. Hence, the polynomial A(x) has a linear factor, i. e. it has a rational root. Lemma 1 is proven.\\r\\n\\r\\nNow let us solve the problem: The number $ pq$ is squarefree (since $ p$ is prime and $ q$ is squarefree, and since $ p\\\\nmid q$).\\r\\n\\r\\nApplying Lemma 1 to the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root. If we denote this root by $ r$, then $ r^n \\\\plus{} ar^{n \\\\minus{} 1} \\\\plus{} pq \\\\equal{} 0$, so that $ pq \\\\equal{} \\\\minus{} r^n \\\\minus{} ar^{n \\\\minus{} 1} \\\\equal{} \\\\minus{} \\\\left(r \\\\plus{} a\\\\right) r^{n \\\\minus{} 1}$ is divisible by $ r^2$ (since $ n\\\\geq 3$ yields $ n \\\\minus{} 1\\\\geq 2$, so that $ r^{n \\\\minus{} 1}$ is divisible by $ r^2$), so that $ r \\\\equal{} 1$ or $ r \\\\equal{} \\\\minus{} 1$ (since $ pq$ is squarefree), so that one of the numbers $ 1$ and $ \\\\minus{} 1$ must be a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$.\\r\\n\\r\\nHence, we see that, if the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers $ 1$ and $ \\\\minus{} 1$ must be a root of this polynomial. Conversely, if one of the numbers $ 1$ and $ \\\\minus{} 1$ is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers $ 1$ and $ \\\\minus{} 1$ is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$. But in fact, $ 1$ is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ if and only if $ 1^n \\\\plus{} a\\\\cdot 1^{n \\\\minus{} 1} \\\\plus{} pq \\\\equal{} 0$, what is equivalent to $ 1 \\\\plus{} a \\\\plus{} pq \\\\equal{} 0$, i. e. to $ a \\\\equal{} \\\\minus{} 1 \\\\minus{} pq$, and $ \\\\minus{} 1$ is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ if and only if $ \\\\left( \\\\minus{} 1\\\\right)^n \\\\plus{} a\\\\cdot\\\\left( \\\\minus{} 1\\\\right)^{n \\\\minus{} 1} \\\\plus{} pq \\\\equal{} 0$, what is equivalent to $ a \\\\equal{} 1 \\\\plus{} \\\\left( \\\\minus{} 1\\\\right)^n pq$. So, the two required values of $ a$ are $ a \\\\equal{} \\\\minus{} 1 \\\\minus{} pq$ and $ a \\\\equal{} 1 \\\\plus{} \\\\left( \\\\minus{} 1\\\\right)^n pq$.\\r\\n\\r\\nThe problem is thus solved.\\r\\n\\r\\n[hide=\\\"Old version of the solution, not generalizing the problem\\\"]\\n\\n[i]Old version of the solution (of the original problem, not of the generalization).[/i]\\n\\nApplying Lemma 1 to the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root, and by a well-known theorem, this integer root then must be a divisor of pq. This means that the root is one of the numbers pq, p, q, 1, -pq, -p, -q, -1. Actually, none of the numbers pq, p, q, -pq, -p, -q can be a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ (in fact, every of these numbers is divisible by p or by q, and if an integer root r of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ would be divisible by p, then $ r^n \\\\plus{} ar^{n \\\\minus{} 1}$ would be divisible by $ p^{n \\\\minus{} 1}$, while $ pq$ wouldn't be because of $ n\\\\geq 3$, so $ r^n \\\\plus{} ar^{n \\\\minus{} 1} \\\\plus{} pq$ couldn't be 0, what yields a contradiction, and similarly we obtain a contradiction if an integer root would be divisible by q). Hence, only 1 and -1 remain as possible candidates for integer roots of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$.\\n\\nHence, we see that, if the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers 1 and -1 must be a root of this polynomial. Conversely, if one of the numbers 1 and -1 is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers 1 and -1 is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$. But in fact, 1 is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ if and only if $ 1^n \\\\plus{} a\\\\cdot 1^{n \\\\minus{} 1} \\\\plus{} pq \\\\equal{} 0$, what is equivalent to $ 1 \\\\plus{} a \\\\plus{} pq \\\\equal{} 0$, i. e. to a = - 1 - pq, and -1 is a root of the polynomial $ x^n \\\\plus{} ax^{n \\\\minus{} 1} \\\\plus{} pq$ if and only if $ \\\\left( \\\\minus{} 1\\\\right)^n \\\\plus{} a\\\\cdot\\\\left( \\\\minus{} 1\\\\right)^{n \\\\minus{} 1} \\\\plus{} pq \\\\equal{} 0$, what is equivalent to $ a \\\\equal{} 1 \\\\plus{} \\\\left( \\\\minus{} 1\\\\right)^n pq$. So, the two required values of a are a = - 1 - pq and $ a \\\\equal{} 1 \\\\plus{} \\\\left( \\\\minus{} 1\\\\right)^n pq$.\\n[/hide]\\r\\n\\r\\n  Darij\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://huggingface.co/datasets/KbsdJames/Omni-MATH","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}