Maths Olympiad Prep

Library / /21 of 34

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

For which positive integers mm does there exist an infinite arithmetic sequence of integers a1,a2,a_1,a_2,\cdots and an infinite geometric sequence of integers g1,g2,g_1,g_2,\cdots satisfying the following properties?
\bullet angna_n-g_n is divisible by mm for all integers n>1n>1 ;
\bullet a2a1a_2-a_1 is not divisible by mm .

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let the arithmetic sequence be {a,a+d,a+2d,}\{ a, a+d, a+2d, \dots \} and the geometric sequence to be {g,gr,gr2,}\{ g, gr, gr^2, \dots \} . Rewriting the problem based on our new terminology, we want to find all positive integers mm such that there exist integers a,d,ra,d,r with mdm \nmid d and ma+(n1)dgrn1m|a+(n-1)d-gr^{n-1} for all integers n>1n>1 .
Note that ma+ndgrn  (1),m | a+nd-gr^n \; (1), ma+(n+1)dgrn+1  (2),m | a+(n+1)d-gr^{n+1} \; (2), ma+(n+2)dgrn+2  (3),m | a+(n+2)d-gr^{n+2} \; (3),
for all integers n1n\ge 1 . From (1) and (2), we have mdgrn+1+grnm | d-gr^{n+1}+gr^n and from (2) and (3), we have mdgrn+2+grn+1m | d-gr^{n+2}+gr^{n+1} . Reinterpreting both equations,
mgrn+1grnd  (4),m | gr^{n+1}-gr^n-d \; (4), mgrn+2grn+1d  (5),m | gr^{n+2}-gr^{n+1}-d \; (5),
for all integers n1n\ge 1 . Thus, mgrk2grk+1+grk+2=grk(r1)2  (6)m | gr^k - 2gr^{k+1} + gr^{k+2} = gr^k(r-1)^2 \; (6) . Note that if mg,rm|g,r , then mgrn+1grnm|gr^{n+1}-gr^n , which, plugged into (4), yields mdm|d , which is invalid. Also, note that (4) ++ (5) gives
mgr(r1)(r+1)2d  (7),m | gr(r-1)(r+1) - 2d \; (7),
so if r±1(modm)r \equiv \pm 1 \pmod m or gr0(modm)gr \equiv 0 \pmod m , then mdm|d , which is also invalid. Thus, according to (6), mg(r1)2m|g(r-1)^2 , with mg,rm \nmid g,r . Also from (7) is that mg(r1)m \nmid g(r-1) .
Finally, we can conclude that the only mm that will work are numbers in the form of xy2xy^2 , other than 11 , for integers x,yx,y ( xx and yy can be equal), ie. 4,8,9,12,16,18,20,24,25,4,8,9,12,16,18,20,24,25,\dots .
~sml1809

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.