For which positive integers $m$ does there exist an infinite arithmetic sequence of integers $a_1, a_2, . . .$ and an infinite geometric sequence of integers $g_1, g_2, . . .$ satisfying the following properties? $a_n - g_n$ is divisible by $m$ for all integers $n \ge 1$; $a_2 - a_1$ is not divisible by $m$. Holden Mui
Problem
Source: USAJMO 2022/1
Tags: USA, USAJMO, number theory, arithmetic sequence, geometric sequence, Sequence, USA(J)MO
24.03.2022 21:11
The solution set is all $m$ such that there exist a prime p with $v_p(m) \geq 2$. First we show that all such $m$ works. Assume $m = p^e \cdot q$, where $p$ is prime and $p\not | \ q$. We can then construct $a_n = 1+(n-1)p^{e-1}q$ and $g_n =(p^{e-1}q+1)^{n-1}$. It is obvious that the second property holds, so we check the first property. By induction, we see that $a_1-g_1=0$ and \begin{align*} g_kp^{e-1}q &\equiv p^{e-1}q &\pmod m\\ g_k(p^{e-1}q+1) &\equiv a_k+p^{e-1}q &\pmod m\\ g_{k+1} &\equiv a_{k+1} &\pmod m \end{align*}completing the induction. Now we show that no other such $m$ works. $m=1$ is absurd. For $m$ being prime, the arithmetic sequences traverses the whole remainder set, meaning there must exist two terms in the geometric such that they are $0,i$ for $i>0$. But that is absurd, as you can not have $0 \cdot n = i$ for some $n$. If $m$ is composite while squarefree, we can use a similar argument with the arithmetic sequences traversing some prime q such that $q | m$ but does not divide the common difference, completing the proof $\blacksquare$.
24.03.2022 21:18
Working $m$ are those that are divisible by the square of any prime. First note you had to make is $a_n \equiv g_n \pmod{m}.$
24.03.2022 21:20
24.03.2022 21:25
Original wording wrote: Find all $m \in \mathbb{Z}^+$ for which there exists an infinite nonconstant sequence in $\mathbb{Z}/m\mathbb{Z}$ that is both arithmetic and geometric. The answer is that $m$ must be divisible by a square number greater than 1. Here are two solutions.
24.03.2022 21:33
24.03.2022 21:47
The answer is $\boxed{m\text{ is not squarefree }}$. Proof of necessity: Suppose $m$ was squarefree. Let the common difference be $d$. We will show that $d^2\mid m$. Consider three terms $a-d,a,a+d$. By the first condition, we must have $(a-d)(a+d)\equiv a^2\pmod m$. So \[a^2-d^2\equiv a^2\pmod m\implies d^2\equiv 0\pmod m\]$\blacksquare$ Proof of sufficiency: Let $m=kp^2$ for a prime $p$. Consider arithmetic as $1,kp+1,2kp+1,\ldots$ and geometric as $1,kp+1,(kp+1)^2,\ldots$. Its easy to check by binomial theorem that this works. $\blacksquare$
24.03.2022 21:50
We claim the answer is $\boxed{\text{all m such that m is not squarefree}}$. Index the sequence at $0$ to make it nicer. Let $a_n=a_0+nd$ for some integers $a_0$ and $d$, and let $g_n=g_0r^n$ for some $g_0$ and $r$. The second condition is $a_1-a_0\not\equiv 0 {\pmod m} \implies d \not\equiv 0\pmod m$. We have \begin{align} g_{n-1} \equiv a_{n-1} \pmod m \\ g_n \equiv a_n \pmod m \\ g_{n+1} \equiv a_{n+1} \pmod m \end{align}Subtracting $(2)-(1)$ gives \begin{align*} g_0r^n-g_0r^{n-1}=g_0r^{n-1}(r-1)\equiv d\pmod{m}, \end{align*}and subtracting $(3)-(2)$ gives \begin{align*} g_0r^{n+1}-g_0r^n=g_0r^n(r-1)\equiv d\pmod{m}. \end{align*}Thus, if we let $x = g_0r^{n-1}(r-1)$, then $$xr\equiv d \pmod{m}\implies dr\equiv d \pmod{m}\implies d(r-1)\equiv 0 \pmod{m}.$$ Suppose $m$ is the product of distinct primes $p_1p_2\dots p_k$. Then, $\gcd(m,r-1)$ is the product of a subset of these primes. In the equivalence $ax\equiv b\pmod{m}$, it is clear that $b$ is divisible by $\gcd(a,m)$. Thus, $d$ is divisible by $\gcd(m,r-1)$. However, since $d(r-1)$ is divisible by $m$, $d$ must also be divisible by all the primes that divide $m$ but not $r-1$. Therefore, $d$ is divisible by $m$, so we have a contradiction. Finally, for a construction when $m$ is not squarefree, let the prime factorization of $m$ be $p_1^{e_1} p_2^{e_2}\dots p_k^{e_k}$, where $e_1 \ge 2$. Then, let $r-1=p_1\implies r=p_1+1$, $d=\tfrac{m}{r-1},$ and $a_0=g_0=\tfrac{d}{r-1}$, which is an integer because $e_1\ge 2$. One can easily show that these two sequences satisfy both properties by induction, so we are done. $\Box$
25.03.2022 09:36
The answer is all non-squarefree positive integers. We split the proof into two parts. Part 1: squarefree numbers don't work. Suppose $m$ is squarefree and such sequences existed. Let $\lambda$ be the difference of $(a_n)$ and $\omega$ the ratio of $(g_n)$. Then, the given conditions rewrite as $m \nmid \omega$ and $m \mid g_1 \lambda ^{n-1}-a_1-\omega(n-1)$ Since $m \nmid \omega$ we infer that $\omega \neq 0$. Furthermore, if $\lambda=1$ then we would have $m \mid a_1+\omega(n-1)$ for all $n$, hence $m \mid \omega$ and $m \mid a_1$, absurd. Thus, we have $\omega \neq 0$ and $\lambda \neq 1$, i.e. $(a_n)$ and $(g_n)$ are not constant. Note that $$\lambda(a_1+\omega(n-1)) \equiv g_1\lambda a^n \equiv a_1+\omega n \pmod m,$$ hence $$\lambda a_1 -a_1-\lambda \omega _(\lambda \omega -\omega)n \equiv 0 \pmod m,$$ for all positive integers $n$, and so we must have $m \mid (\lambda-1)\omega$ and $m \mid (\lambda-1)a_1-\lambda \omega$ Now, since $m \nmid \omega $ and $m$ is squarefree, we may pick a prime $p$ dividing $m$ but not $\omega$. Since $p \mid m \mid (\lambda-1)\omega$, this implies $p \mid (\lambda-1)$, and so by the second divisibility condition $p \mid \lambda \omega$, which is a contradiction since $p \nmid \omega$ and $p \nmid \lambda$ (because it divides $\lambda -1$). Part 2: non-squarefree numbers work. Indeed, if $m$ is not squarefree we may write $m=x^2y$ with $x>1$, and pick $(a_n)$ and $(g_n)$ as follows: $a_1=1$ and common difference $xy$ and $g_1=x^2y+1$ and common ratio $x^2y+xy+1$ Since $x>1$, the second condition is evidently satisfied, while for the first it is a simple induction exercise to prove it is satisfied, too. Thus, the only solutions are all non-squarefree positive integers.
25.03.2022 10:28
We claim that only non-square free numbers work. Write $a_n-g_n=a+nd-cr^{n-1}$($d$ is the common difference).Now,assume $m$ is squarefree.By given condition,we can choose a $p|m$ ,not dividing $d$.Then choose $n=p$,if $n|r$,then $n|a$,which doesn't work.So we get that $a \equiv c \pmod p$.Now,we we choose $n \equiv d^{-1} \pmod p$,and $n \equiv 1 \pmod {p-1}$,by CRT,to get a contradiction. For $m=kp^2$,for some prime $p$,choose $a=1,d=kp,c=r=(1+kp)$
25.03.2022 20:44
Also here Only non-squarefree positive integers greater than 1 will work.Let us assume $a_n=an+b$,$g_n=kr^n$ for all $n\ge 1$.Let $p$ be a prime divisior of $m$.From the first condition of the problem, $$an+b\equiv kr^n\pmod{p}\qquad(*)$$ If $r$ is divisible by $p$ then putting $n=p$ in (*) we get $b$ is divisible by $p$ which means $an$ is divisible by $p$ for all $n$,which implies $p|a$. If $p\nmid r$ then putting $n=1$ in (*) gives $p\mid kr-a-b$ and putting $n=p$ in (*) and using fermat's little theorem gives $p\mid kr-b$.So this implies $p\mid a$. From these observations,we get, When $m=p_1p_1\dots p_s$ is squrefree then $p_i\mid a$ for all $i=1,2,\dots ,s$.So $m\mid a$,but then $m\mid a_2-a_1=a$. When $m$ is non-squrefree then $m=p^ct$ where $c>1$ and $\gcd (p,t)=1$.Take $a=p^{c-1}t,b=1,r=p^{c-1}t+1,k=1$.Observe that $p^ct\nmid a_2-a_1=p^{c-1}t$.Also,using binomial theorem, $$a_n=p^{c-1}tn+1\equiv (p^{c-1}t+1)^n=g_n\pmod{p^ct}$$ We are done.$\blacksquare$
25.03.2022 21:11
copying here The answer is $\boxed{m\text{ is not squarefree }}$. Proof of necessity: Suppose $m$ was squarefree. Let the common difference be $d$. We will show that $d^2\mid m$. Consider three terms $a-d,a,a+d$. By the first condition, we must have $(a-d)(a+d)\equiv a^2\pmod m$. So\[a^2-d^2\equiv a^2\pmod m\implies d^2\equiv 0\pmod m\]$\blacksquare$ Proof of sufficiency: Let $m=kp^2$ for a prime $p$. Consider arithmetic as $1,kp+1,2kp+1,\ldots$ and geometric as $1,kp+1,(kp+1)^2,\ldots$. Its easy to check by binomial theorem that this works. $\blacksquare$
25.03.2022 21:45
lol i showed that every prime factor of m also has to be a prime factor of d and since m does not divide d, it can't be squarefree otherwise, it will cycle and the geometric sequence must go from being a multiple of something to not being a multiple of something, which is impossible as the ratio is an integer
25.03.2022 22:51
The answer is 1, and all numbers $n>1$ which are not primes and products of distinct primes. First we show all of the above work. Suppose $p$ is the smallest prime such that $\nu_p(m) \geq 2$; then, choose the common difference $d$ of $\{a_n\}$ to be $\frac mp$. Letting $a_1=1$, the sequence $\{a_n\}$ cycles$$1, 1+\frac mp, 1 + \frac{2m}p, \cdots, 1+\frac{(p-1)m}p, 1, \cdots.$$Now let $g_1=1$, and the common ratio $r$ of $\{g_n\}$ be $1+\frac mp$. I claim $g_n \equiv a_n \pmod m$ for all $n$. This is doable by induction: the base case(s) $n=1, 2$ are obvious, while$$g_{k+2} = \left(1+\frac{km}p\right)\left(1+\frac mp\right) = 1+\frac{km^2}{p^2}+\frac{(k+1)m}p \equiv 1 + \frac{(k+1)m}p \equiv m$$because $\nu_p(m^2) \geq 4$ by construction. Thus all such integers work. Now, to show the other integers fail, consider the following Claim. Suppose $d$ is such that there exists a prime $p$ with $p \mid m$ and $p \nmid d$. Then $d$ cannot possibly be the common difference. Assume for the sake of contradiction the opposite. Then there exists an $a_k$ with$$p \mid a_k = a_1 + (k-1)d$$by CRT because $\gcd(p, d) = 1$. So $p \mid g_k$ as well, so$$p \mid g_{k+1} \iff p \mid a_{k+1} = a_k + d$$as $p \mid m$. This implies $p \mid d$, contradiction. $\blacksquare$ However, for all integers $k < m$ modulo $m$, $d$ must satisfy the above property. (If $d$ contains all the prime factors of $m$, the smallest possible value of $d$ is $m$.) We are done.
26.03.2022 03:53
:clown: when throw in actual test Consider the valid construction $m=pq^2$ for prime q. Let our infinite arithmetic sequence and geometric sequence be $1,pq+1, 2pq+1, \ldots, npq+1, \ldots$ and $1,pq+1,(pq+1)^2, \ldots, (pq+1)^n, \ldots.$ Therefore $m$ that are non-squarefree work. Claim: Values $m$ that are squarefree fail. Proof. Rewrite the values of the arithmetic sequence as $a_1, a_1+b, \ldots, a_1+(n-1)b$ and geometric sequence $g_1, g_1r, \ldots, g_1r^{n-1}.$ From $m \mid a_n-g_n,$ we know $a_n \equiv g_n \pmod{m}.$ Therefore, \begin{align} a_1 &\equiv g_1 \pmod m, \\ a_1+b &\equiv g_1r \pmod m, \\ a_1+2b &\equiv g_1r^2 \pmod m. \end{align}Adding $(1)$ to $(3),$ we obtain $2a_1+2b \equiv 2\cdot (2) = 2g_1r \equiv g_1+g_1r^2 \pmod{m}.$ We subtract congruences to obtain $g_1 + g_1r^2 - 2g_1r = g_1(r-1)^2 \equiv 0 \pmod{m},$ videlicet, $m \mid g_1(r-1)^2.$ In order for this to occur, we must either have $g_1 \equiv 0 \pmod{m}$ or $r-1 \equiv 0 \pmod{m} \implies r \equiv 1 \pmod{m}.$ Define the prime factorization of $m$ to be $p_1p_2\cdots p_k,$ where every factor $p_i$ is distinct. Consider $(2)-(1).$ We obtain $b \equiv g_1r-g_1 = g_1(r-1) \pmod{m}.$ Recall $g_1(r-1) \equiv 0 \pmod{m}$ above, so $m \mid b.$ However, from the second condition that $m \nmid a_2-a_1,$ we know $b \not \equiv 0 \pmod{m},$ a contradiction. $\blacksquare$ In hindsight, this problem wasn't too bad.
26.03.2022 03:57
Let $a_n=a_1+d(n-1)$ and $g_n=g_1r^{n-1},$ noting $m\nmid d.$ Then, $a_1+d(n-1)-g_1r^{n-1}\equiv 0\pmod{m}$ for all $n\ge 1$ so taking $n=k+1$ and $n=k,$\begin{align*}&a_1+d(k-1)-g_1r^{k-1}\equiv a_1+dk-g_1r^k\pmod{m}\\&\iff d\equiv r^{k-1}(r-1)g_1\pmod{m}\quad (*)\end{align*}for all $k\ge 1.$ Hence, $r^{k-1}(r-1)g_1\pmod{m}$ is constant for all $k\ge 1$ and thus $(r-1)g_1\equiv r(r-1)g_1\pmod{m}$ or$$g_1(r-1)^2\equiv 0\pmod{m}.$$Notice $g_1(r-1)\not\equiv 0\pmod{m}.$ Suppose $m$ is squarefree. We know all divisors of $m$ are squarefree, so $\gcd((r-1)^2,m)=\gcd(r-1,m).$ Hence, $$m=\gcd(g_1(r-1)^2,m)=\gcd(g_1(r-1),m)\neq m.$$We have reached a contradiction and so $m$ being not squarefree is necessary. Suppose $m$ is not squarefree; that is, $m=a^2b$ with $a>1$ and $b$ squarefree. Choose $r=a+1,g_1=b,$ and $d=(a+1)ab.$ Then,$$r^{k-1}(r-1)g_1\equiv (a+1)^{k-1}ab\equiv (1+(k-1)a)ab\equiv ab\equiv d\pmod{m}$$for all $k\ge 1.$ From $(*),$ we have$$a_k-g_k\equiv a_1+d(k-1)-g_1r^{k-1}\equiv a_1+dk-g_1r^k\equiv a_{k+1}-g_{k+1}\pmod{m}.\quad (**)$$Let $a_1$ be such that $a_1-g_1\equiv 0\pmod{m}.$ We proceed by induction to show that this construction works. For our base case, $m\mid a_1-g_1$ by definition. Also, $a_k-g_k\equiv a_{k+1}-g_{k+1}\pmod{m}$ by $(**),$ so our induction is complete. We see $d\equiv ab\not\equiv 0\pmod{m}$ so we have shown $m$ being not squarefree is sufficient. $\square$
26.03.2022 04:46
How hard is this problem? Maybe around 5in MOHS?
26.03.2022 04:47
JingheZhang wrote: How hard is this problem? Maybe around 5in MOHS? 5 or 10 probably
26.03.2022 04:53
megarnie wrote: JingheZhang wrote: How hard is this problem? Maybe around 5in MOHS? 5 or 10 probably I see. I feel that it's a little bit harder than average JMO 1/4.
27.03.2022 07:04
I'm transcribing as written from the solution I submitted during the test. Does it get a 7? (I'm aware it's weirdly phrased sometimes)
27.03.2022 09:46
A bit too hard for jmo1, Took about 1.5 hours for this. We claim $m$ must be a non-square free. Assumes for simplicity that $x=a_2-a_1$ and $y=g_2-g_1$. Case 1. $m$ is a square free. Since $m\nmid x$ and $m$ is a square free, there is a prime $p$ where $p|m$ and $p\nmid x$. Consider\[m|a_p-g_p\implies p|a_p-g_p\implies p|(p-1)x-a_1(y^{p-1}-1)\implies p|x+a_1(y^{p-1}-1)\]Since $p\nmid x$, and by Fermat's theorem, we have $p|y$. Hence $p\nmid x+y.$ But \[p|(a_1-g_1),p|(a_2-g_2)\implies p|a_1-a_2-g_1+g_2\implies p|x+y\]leads to a contradiction. Case 2. $m$ is a non-square free. Let $m=ka^2$ for some natural numbers $k,a$. Consider sequences $(a_n)=nak+1$ and $(g_n)=(ak+1)^n$, we have \[a_n-g_n=nak+1-(ak+1)^n\equiv 0\pmod{ka^2}\]for each $n=1,2,3,\dots$. Thus the answer is that $m$ is a non-square free as desired.
30.03.2022 18:40
Let $\equiv$ denote equivalence$\pmod m$. Note that $a_n\equiv g_n$. Then $a_n\cdot a_{n+2}\equiv a_{n+1}^2$, or, where, $a_n=a+nd$: $$(a+nd)(a+nd+2d)\equiv(a+nd+d)^2\Leftrightarrow d^2\equiv0.$$Then since $m\nmid d$, $m$ must be squareful. Let $m=a^2b$, then:
23.04.2022 11:12
: Let $d$ be the common difference of sequence $a$. The second condition is $m\nmid d$. Let $r$ be the common ratio of sequence $g$. Claim: $r$ is an integer. Proof. Suppose $r$ is not an integer. Then there must exist a prime $p$ such that $\nu_p(r)\le-1$. Choose a positive integer $k$ such that $k-1>\nu_p(g_1)$. We have $$\nu_p(g_k)=\nu_p(g_1r^{k-1})=\nu_p(g_1)+\nu_p(r^{k-1})=\nu_p(g_1)+(k-1)\nu_p(r)\le\nu_p(g_1)-(k-1)<0.$$Therefore, $g_k$ is not an integer, which is absurd, so $r$ must be an integer. $\blacksquare$ Claim: Sequences $a$ and $g$ satisfying the properties exist iff $m$ is divisible by the square of a prime. Proof. First, we show all such $m$ work. Let $p$ be a prime such that $p^2\mid m$. Then, let \begin{align*} a_1=g_1&=\frac{m}{p^2} \\ d&=\frac m p \\ r&=p+1 \\ \end{align*}Since $m\nmid \frac m p=d$, the second condition is satisfied. Note that $rd-d=(p+1)\frac{m}{p}-\frac{m}{p}=m$, so $$rd-d\equiv0\pmod{m} \qquad (1)$$To show $a_n\equiv g_n\pmod{m}$ for all integers $n\ge1$, we use induction. Since $a_1=g_1$, $a_1\equiv g_1\pmod{m}$. Since $a_2 = a_1+d=\frac{m}{p^2}+\frac{m}{p}$, and $g_2=rg_1=(p+1)\frac{m}{p^2}=\frac{m}{p^2}--\frac{m}{p}$, $$a_2=g_2\implies a_2\equiv g_2\pmod{m}.$$Now suppose $a_{k-1}\equiv g_{k-1}\pmod{m}$ and $a_k\equiv g_k\pmod{m}$ for integral $k\ge2$. Then, \begin{align*} a_{k+1} &= a_k+d&\\ &\equiv g_k + d&\\ &= rg_{k-1} + d&\\ &= r(g_{k-1}+d)-(rd-d)&\\ &\equiv r(g_{k-1}+d) &\text{By }(1)\\ &\equiv r(a_{k-1}+d)&\\ &= ra_k&\\ &\equiv rg_k=g_{k+1}\pmod{m}.&\\ \end{align*}This finishes the inductive step, so we have shown the first condition is satisfied. Hence, all such $m$ work. Now, we show that $m$ must be divisible by the square of a prime. The first property tells us \begin{align*} a_1 &\equiv g_1\pmod{m} &(2)\\ a_2 \equiv g_2 &\implies a_1+d\equiv g_1r\pmod{m} &(3)\\ a_3 \equiv g_3 &\implies a_1+2d\equiv g_1r^2\pmod{m} &(4)\\ \end{align*}Subtracting $(2)$ from $(3)$, we get \begin{align*} d &\equiv g_1r-g_1\pmod{m} &(5)\\ rd &\equiv g_1r^2 - g_1r\pmod{m} &\\ \end{align*}Subtracting $(3)$ from $(4)$, we get $$d\equiv g_1r^2-g_1r\pmod{m}$$Therefore, $rd\equiv d\pmod{m}$, so $$m\mid d(r-1) \qquad (6)$$Since we only care about the sequences modulo $m$, WLOG we can assume $$d,r\in [0,m-1]$$Since $m\nmid d$, $d\neq 0$, so $d\in [1,m-1]$. $\qquad$ If $r=0$ or $1$, then $g_2$ would be equal to $g_3$, so $d=a_3-a_2\equiv g_3-g_2\equiv0\pmod{m}$, contradiction, so $r\in [2, m-1]$. Claim: $\gcd(m,r-1)\mid d$. Proof. From $(5)$, we have \begin{align*} m&\mid g_1r-g_1-d\\ m&\mid g_1(r-1)-d\\ \end{align*}If $\gcd(m,r-1)\nmid d$, then since $\gcd(m,r-1)\mid r-1$, $$\gcd(m,r-1)\nmid g_1(r-1)-d,$$which is absurd because $\gcd(m,r-1)\mid m$. Thus, $\gcd(m,r-1)\mid d$. $\blacksquare$ Now suppose $m$ is square-free. Then for every prime dividing both $m$ and $r-1$, it divides $\gcd(m,r-1)$, so it divides $d$. Since $m\mid d(r-1)$, every prime factor that of $m$ must divide either $d$ or $r-1$, so every prime factor of $m$ must divide $d$. Since $m$ is square-free, $m\mid d$, which contradicts the second property. So we have shown that if $a$ and $g$ exist, $m$ is divisible by the square of a prime. $\blacksquare$
19.09.2022 06:11
The answer is only those positive integers $m > 1$ which are not squarefree. Clearly $m = 1$ fails, so henceforth assume $m > 1$.
17.02.2023 04:45
how many points would this receive? Let $a_n = a_1 + (n-1)d$ where $m \nmid d$ and $g_n = g_1r^{n-1}$. We are given the condition that for all $n$ \[a_1 + (n-1)d = g_1r^{n-1} \pmod{m}.\]Since $a_1 \equiv g_1 \pmod{m}$, we know that \[g_1 + (n-1)d \equiv g_1r^{n-1} \pmod{m}.\]Since \[g_1 + d \equiv g_1r \pmod{m} \Rightarrow d \equiv g_1(r-1) \pmod{m}.\]So we know that for all $n$,\[g_1 + g_1(n-1)(r-1) \equiv g_1r^{n-1} \pmod{m}.\]If $g_1 \equiv 0 \pmod{m}$ this works for all $m$ so we will assume $g_1 \not\equiv 0 \pmod{m}$. Hence \[1 + (n-1)(r-1) \equiv r^{n-1} \pmod{m}.\]We know that $(r-1)^2 \equiv 0 \pmod{m}$ from $a_3 \equiv g_3 \pmod{m}$ and $r- 1 \not\equiv 0 \pmod{m}$ since $m \nmid d$. Therefore we know that $m = p^2 \cdot q$ for integers $p > 1$ and $q$. Now we show that this actually works. Assume $m = p_1p_2 \cdots p_k$ and we will prove that this doesn't work. We know that $d \equiv g_1(r-1) \pmod{p_1p_2p_3 \dots p_k}$ and $g_1(r-1)^2 \equiv 0 \pmod{p_1p_2p_3 \dots p_k}$. From the second congruence we see that $r \equiv 1 \pmod{p_i}$ but this is a contradiction since then $d \equiv 0 \pmod{m}$ which is not true. Hence $m$ must be of the form $p^2 \cdot q$.
31.03.2023 15:15
We claim that the set of $m$ satisfying the question is those where there exists a prime $p$ so that $v_p(m)\geq 2$. We first let $a_n=a_1+d(n-1)$ and $g_n=g_1r^{n-1}$. Then $m\nmid a_2-a_1$ means $m\nmid d$ and $$m\mid a_n-g_n$$$$\implies m\mid a_1+d(n-1)-g_1r^{n-1}$$$$\implies m\mid (g_1r^2-a-2d)-2(g_1r-a-d)+(g_1-a)$$$$\implies m\mid g_1(r-1)^2$$ In addition, we also have: $$m\mid (g_1r-a-d)-(g_1-a)$$$$\implies m\mid g_1(r-1)-d$$$$\implies m\nmid g_1(r-1)$$ Now assume that for all prime factor $p$ of $m$, $v_p(m)=1$. Then since $m\mid g_1(r-1)^2$, $m\mid g_1$ or $m\mid r-1$. This means that $m\mid g_1(r-1)$, contradiction. Now we construct the sequence $(a_n)$ and $(r_n)$ for $m$ where there exists a prime $p$ so that $v_p(m)\geq 2$. Let $b=\frac{m}{p}$, then $v_p(b)\geq 1$ and $v_p'(b)=v_p'(m)$ for all other prime factor $p'$ of $m$. Then it's obviois that $m\mid b^2$. Now we set: $$a_n=1+b(n-1)$$$$g_n=(b+1)^{n-1}$$ Then $a_2-a_1=b-1$ which is not divisible by $p$ and therefore is not divisible by $m$. We now prove that $m\mid a_n-g_n$ by induction by $n$. The case of $n=1,2$ is trival as $a_n-g_n=0$. Then: $$(g_{n+2}-a_{n+2})-2(g_{n+1}-a_{n+1})+(g_n-a_n)$$$$=g_{n+2}-2g_{n+1}+g_n$$$$=(b+1)^{n+1}-2(b+1)^n-(b+1)^{n-1}$$$$=(b+1)^{n-1}b^2$$ which is divisible by $m$. Therefore if the statement is true for $n$ and $n+1$, it is also true for $n+2$. Thus the statement is proven and the solution is complete.
19.05.2023 09:15
$a_{n+1}=x*n+a_1$ $g_{n+1}=g_1*y^n$ $x$ not div $m$ $x*n+a_1-g_1*y^{n} \equiv 0 \pmod m$ $x*(n+1)+a_1-g_1*y^{n+1} \equiv 0 \pmod m$ Subtacting those two gives $x-g_1*y^n*(1-y) \equiv 0 \pmod m$ $x \equiv g_1*y^n*(1-y) \pmod m$ $g_1*y^n*(1-y) \pmod m$ is constant and nonzero, so $1-y$ cannot divide $m$ So $g_1*(1-y) \equiv g_1*(1-y)*y \pmod m$ So $0 \equiv g_1*(1-y)*(y-1) \pmod m$ So $0 \equiv g_1*(1-y)^2 \pmod m$ So $0 \equiv (1-y)^2 \pmod m$ but $1-y$ not div $m$ If $m$ does not have a square in its prime factorization, squaring a number does not introduce any new factors, so if a number does not divide $m$, it squared would also not divide $m$ However, if $m$ has a squared term or more in its prime factorization, then squaring a number not divisible by $m$ increase the power of the factors, so the square can divide $m$ So $\boxed{m \text{ is not square free}}$ Let $m=p^2*q$
Let $y=pq+1, x=pq, a_1=1, g_1=1$ So a non square free $m$ always works
20.08.2023 04:14
We claim that $m$, must be divisible by a perfect square, greater than $1.$ Let the common difference, be $d.$ If we take the terms $(a-d), a, (a+d)$, so $(a-d)(a+d) \equiv a^2 \pmod {m}$, so we have, $d^2 \equiv 0 \pmod {m}$, which finishes, hence, proved. Now the sequence, $1, kp+1, 2kp+1, 3kp+1.....$, for a constant $k$, such that $m=kp^2$, and $1, kp+1, (kp+1)^2, (kp+1)^3,....$, it is easy to check, that this works. oops probably missed smth since too simple.....
05.12.2023 05:00
05.12.2023 05:44
We claim that all squarefree $m$ fail. To see this take some $m$ and a prime factor $p$. Let $a_i = x + (i-1)d$, for some integer $d$ not divisible by $m$. Similarly let $g_i = yr^{i-1}$. Now note by taking $i = 1$ we find, $$x \equiv y \pmod{m}$$Then consider some prime factor of $m$, which we will call $p$. Note from the equivalence $\text{mod } m$, we have $x$ and $y$ are equivalent $\text{mod } p$. Now taking $i = p$ we find, $$x \equiv d + y \pmod{p}$$However clearly then $d \equiv 0 \pmod{p}$. Thus if $\nu_p(m) \leq 1$ for all prime $p$, we will have $m \mid d$, a contradiction. Now we provide a construction for $m$ that are not squarefree. For construction let $m = kp^2$. Then take the sequences, \begin{align*} a_i &= 1 + (i-1)kp\\ g_i &= (kp+1)^{i-1} \end{align*}
26.01.2024 05:53
The answer is all non-squarefree $m>1$. The conditions are equivalent to $a_1 \equiv g_1 \pmod{m}$ $d \not\equiv 0 \pmod{m}$ $d-(r-1)g_n \equiv 0 \pmod{m}$ for all $n \ge 1$, where $d$ and $r$ represent the usual common difference and common ratio. Assume for contradiction that $m$ is square free. Let $p$ be a prime divisor of $m$ such that $p \nmid d$. Then \[ (r-1)g_n \equiv d \not\equiv 0 \pmod{p} \]for all $n \ge 1$, so $g_n$ is always not divisible by $p$. However, since $\gcd(d, p)=1$, there exists an index $j$ for which $a_j=0$. This means that $p \nmid (a_j-g_j)$, a contradiction. We finish with a construction. Let $m=p^2 \cdot \ell$ for some prime $p$ and integer $\ell$. Let $a_i=1+ip\ell$ and $g_i=(1+p\ell)^{i-1}$. It is easy to verify that this works.
01.03.2024 07:15
02.03.2024 11:12
All nonsquarefree $m$ work, and these are the only $m$ that work. Construction: Let $m = p^2 k$ for some $k \in \mathbb{N}$ and $p$ a prime. Cosider $a_i = 1 + ipk$ and $g_i = (1+pk)^i$ for all $i.$ Then \[ g_i - a_i \equiv (1+pk)^i - 1 - ipk \equiv 1 + ipk + p^2 k^2 (\text{something}) - 1 - ipk \equiv p^2 k^2 (\text{something}) \equiv 0 \pmod{m} \]by the Binomial Theorem and $a_2 - a_1 \equiv pk \not \equiv 0 \pmod{m},$ proving sufficiency. Proof that none other work: Assume that $m$ is a squarefree integer. Let our geometric sequence be $a, ar, ar^2, \dots$ for some positive integer $a$ and $r$; then our arithmetic sequence (mod $m$) must be $a, ar, 2ar - a, \dots.$ Therefore, we have \[ ar^2 \equiv 2ar - a \pmod{m}. \]Rearranging and factoring gives \[ a(r-1)^2 \equiv 0 \pmod{m}. \]However, we are given that $a_2 - a_1 \equiv a(r-1) \not \equiv 0 \pmod{m}.$ Thus $a(r-1)$ doesn't have all of the prime factors of $m.$ Since $m$ is squarefree, that implies that $a(r-1)^2$ doesn't either, which is a clear contradiction. Therefore, the only $m$ that work are those that are nonsquarefree.
06.03.2024 04:10
The answer is all non-square-free positive integers. Necessity. If $m=p_1p_2\dots p_k$, there exists a $p_i$ not dividing the common difference of $\{a_i\}$, so that $\{a_i\}$ cycles through all the residues modulo $p$ which precludes a corresponding geometric sequence. Sufficiency. If $p^2\mid m$, the geometric sequence $(\tfrac{m}{p}+1)^i$ generates $\tfrac{m}{p}+1,\tfrac{2m}{p}+1,\dots$. $\square$
15.03.2024 03:42
The answer is all non-squarefree positive integers. Proof: If the arithmetic sequence has difference $d$, we clearly must have $\gcd(d, m) < m$ or else it is constant. Then, there exists some divisor of $m$ (say, $d_0$) such that $\gcd(d, d_0) = 1$. Then, the arithmetic sequence cycles through all possible residues modulo $d_0$, which is not possible for a geometric sequence. Construction: For any non-squarefree $m$, take any $n$ such that $m \mid n^2$ but $m \nmid n$; then, by binomial theorem we have \[ (n+1)^k \equiv kn+1 \pmod{m} \]which suffices.
31.08.2024 20:40
Consider some three elements $A$, $A + b$, $A + 2b$ modulo $m$ that must be in arithmetic and geometric progression. Then $\frac{A}{A+b} \equiv \frac{A+b}{A+ 2b} \implies A(A+2b) \equiv (A+b)^2 \implies b^2 \equiv 0\pmod{m}$. Since $b \equiv 0\pmod{m}$ is impossible, we must have $1 \leq \nu_p(b) < \nu_p(m)$ for some $p$. This implies that $m$ cannot be squarefree. We will show that all squarefree numbers work. We will show that the sequence $1$, $1 + \frac{n}{p}$, $\dots$ works for some $p$ given $\nu_p(m) \geq 2$. It suffices to show that $1 + \frac{kn}{p} \equiv \left(1 + \frac{n}{p}\right)^k$. However, by binomial theorem, all terms of $\left(1 + \frac{n}{p}\right)^k$ vanish modulo $m$ except for $1$ and $\binom{k}{1} \cdot \frac{n}{p} = \frac{kn}{p}$, so we are done.
23.12.2024 19:12
Call the first term of the geometric series $g$, the common ratio $r$, the first term of the arithmetic sequence $a$ and the common difference $d$. $$gr^k \equiv a + kd \pmod{m}, gr^{k+1} \equiv a+(k+1)d \pmod{m} \implies gr^k(r-1) \equiv d \not \equiv 0 \pmod{m}$$We also have since this is equivalent to the geometric sequence having an arithmetic sequence of residues modulo $m$ we have: $$2gr^{k} \equiv gr^{k+1} + gr^{k-1} \equiv{m} \implies gr^{k-1} (r-1)^2 \equiv 0 \pmod{m} $$So there exists a prime $p$ that divides $r-1$ such that $\nu_p (m) \ge 2$. So if $m$ is squarefree this fails. If $m$ isn't squarefree just let $m=p^2 \cdot n$ for some $p$, and $n$. Take $g=n$, $r=p+1$, $d=pn$, $a=n$. Then we have $$a_2-a_1 = d \not \equiv 0 \pmod{m}$$$$a_k-g_k = n(p+1)^k -n -pnk -m \equiv n((p+1)^k -pk-1) \equiv n(\tbinom{k}{1}p+1-pk-1) \equiv 0 \pmod{p^2 n}$$Therefore the answer is all $m$ not squarefree.