We call a positive integer $n$ amazing if there exist positive integers $a, b, c$ such that the equality \[n = (b, c)(a, bc) + (c, a)(b, ca) + (a, b)(c, ab)\] holds. Prove that there exist $2011$ consecutive positive integers which are amazing. Note. By $(m, n)$ we denote the greatest common divisor of positive integers $m$ and $n$.
Problem
Source: Middle European Mathematical Olympiad 2011 - Team Compt. T-8
Tags: modular arithmetic, greatest common divisor, arithmetic sequence, number theory, relatively prime, algebra, system of equations
07.09.2011 22:15
$ (b,c)(a,bc)=(a,b)(a,c) $ so $ n=xy+yz+zx $. if we take the numbers $ 2011!+1,2011!+2,....,2011!+2011 $ then we can take $ x=1,y=t-1 $ for $ 2011!+t-1 $.
08.09.2011 07:34
anonymouslonely wrote: $ (b,c)(a,bc)=(a,b)(a,c) $ For $a=1$,$b=c=2$, $(a,b)(a,c)=1$, but $(b,c)(a,bc)=2$.
10.09.2011 20:21
A solution: Let $f(a,b,c):=(b, c)(a, bc)+(c, a)(b, ca)+(a, b)(c, ab)$. Consider $f(a,a,b)$: \[f(a,a,b)=a((a^2, b)+2(a, b))=a(a, b)\left(2+\frac{(a^2, b)}{(a, b)}\right).\] Let $a=a'p^{\alpha}$ ($(a', p)=1$), $b=p^{\alpha+1}$, $p$ prime. Then $(a, b)=p^{\alpha}$ and $(a^2, b)=p^{\alpha+1}$. Hence \[f(a,a,b)=a'p^{\alpha}(2+p)=cp(p+2),\] where $c$ is an arbitrary integer, $p$ an arbitrary prime. Now choose primes $p_i$, ($1\le i \le 2011$), such that $(p_i(p_i+2), p_j(p_j+2))=1$ for $i\ne j$. Suppose we've chosen $p_i$ for $1\le i \le k$. Prime $p_{k+1}$ must satisfy $(p_{k+1}+2, \prod_{1}^{k} p_i(p_i+2))=1$. Consider the arithmetic progression $n\prod_1^kp_i(p_i+2)-1$. Using a well-known theorem of Dirichlet, this progression contains infinitely many primes. Choose one of those primes and name it $p_{k+1}$. Then $p_{k+1}+2=n\prod_1^kp_i(p_i+2)+1$ is clearly relatively prime to $\prod_1^kp_i(p_i+2)$. Now consider the following system of equations: \[x+i\equiv 0 \pmod{p_i(p_i+2)}\] for $1\le i \le 2011$. Due to the chinese remainder theorem, this system has a solution giving us $2011$ consecutive amazing integers.
10.09.2011 20:57
yunxiu wrote: anonymouslonely wrote: $ (b,c)(a,bc)=(a,b)(a,c) $ For $a=1$,$b=c=2$, $(a,b)(a,c)=1$, but $(b,c)(a,bc)=2$. sorry,my mistake...
13.09.2011 04:42
FelixD wrote: A solution: Let $f(a,b,c):=(b, c)(a, bc)+(c, a)(b, ca)+(a, b)(c, ab)$. Consider $f(a,a,b)$: \[f(a,a,b)=a((a^2, b)+2(a, b))=a(a, b)\left(2+\frac{(a^2, b)}{(a, b)}\right).\] Let $a=a'p^{\alpha}$ ($(a', p)=1$), $b=p^{\alpha+1}$, $p$ prime. Then $(a, b)=p^{\alpha}$ and $(a^2, b)=p^{\alpha+1}$. Hence \[f(a,a,b)=a'p^{\alpha}(2+p)=cp(p+2),\] where $c$ is an arbitrary integer, $p$ an arbitrary prime. Maybe: Then $(a, b)=p^{\alpha}$ and $(a^2, b)=p^{\alpha+1}$. Hence \[f(a,a,b)=a'p^{2\alpha}(2+p)\]
01.09.2016 18:10
we can write f(a,a,b)=cp^2(p+2) and the proven is anlogously