Maths Olympiad Prep

Library / /20 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, . . . and an infinite geometric sequence of integers g1,g2,...g_1, g_2, . . . satisfying the following properties?
[list]
[*] angna_n - g_n is divisible by mm for all integers n1n \ge 1;
[*] a2a1a_2 - a_1 is not divisible by mm.
[/list]
[i]Holden Mui[/i]

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

Solution

Given:

1. An infinite arithmetic sequence of integers a1,a2, a_1, a_2, \ldots with the common difference d=a2a1 d = a_2 - a_1 .
2. An infinite geometric sequence of integers g1,g2, g_1, g_2, \ldots with the common ratio r1 r \neq 1 .
3. The condition that angn a_n - g_n is divisible by m m for all n1 n \geq 1 .
4. The further condition that d d (the common difference) is not divisible by m m .

We need to determine for which positive integers m m these conditions hold.

### Analysis

Arithmetic and Geometric Sequences:
- For the arithmetic sequence, we have:
an=a1+(n1)d. a_n = a_1 + (n-1)d.
- For the geometric sequence, we have:
gn=g1rn1. g_n = g_1 \cdot r^{n-1}.

Difference Condition:
The condition angn0(modm) a_n - g_n \equiv 0 \pmod{m} implies:
a1+(n1)dg1rn10(modm). a_1 + (n-1)d - g_1r^{n-1} \equiv 0 \pmod{m}.

Rewriting, this gives:
a1g1(g1rn1(n1)da1)0(modm). a_1 - g_1 \equiv (g_1r^{n-1} - (n-1)d - a_1) \equiv 0 \pmod{m}.

### Divisibility Argument

The first condition angn0(modm) a_n - g_n \equiv 0 \pmod{m} holds for all n n if and only if a1g1(modm) a_1 \equiv g_1 \pmod{m} and

n,(n1)dg1(rn11)(modm). \forall n, \quad (n-1)d \equiv g_1 (r^{n-1} - 1) \pmod{m}.

For the second sequence property a2a1≢0(modm) a_2 - a_1 \not\equiv 0 \pmod{m} , this indicates d≢0(modm) d \not\equiv 0 \pmod{m} .

Condition Conclusions:

- If m m is squarefree, then every divisor of m m is prime, such that rn110(modp) r^{n-1} - 1 \equiv 0 \pmod{p} (for any prime divisor p p ) forces r1(modp) r \equiv 1 \pmod{p} , contradicting the non-zero difference condition since otherwise, all differences (n1)d (n-1)d would need to be zero modulo m m .

- If m m is not squarefree, i.e., m m contains a repeated prime factor p2 p^2 , we can choose r1(modp) r \equiv 1 \pmod{p} but r≢1(modp2) r \not\equiv 1 \pmod{p^2} , allowing for the divisibility of differences to meet all conditions without d0(modm) d \equiv 0 \pmod{m} .

### Conclusion

Thus, m m must be not squarefree for these sequences with the conditions given to exist.

m is not squarefree \boxed{\text{m is not squarefree}}

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.