

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Let $f(n)$ be an arithmetic function with period $q$ such that $f(n)=0$ whenever $(n,q)>1$. Call $d$ a quasiperiod of $f$ if $f(m)=f(n)$ whenever $m\equiv n \bmod d$ and $(mn,q)=1$.

Suppose $d_1$ and $d_2$ are quasiperiods, put $g=(d_1, d_2)$, and suppose that $m\equiv n \bmod g$ and $(mn,q)=1$.

Now I would like to prove that:

There exist integers $a$ and $b$ such that $m=n+ad_1+bd_2$ and $(n+ad_1,q)=1$. Any comments are welcome.


share|cite|improve this question
I just realized this is Exercise 1(a) from Section 9.1.1 in Montgomery-Vaughan: Multiplicative Number Theory I. – GH from MO Feb 28 at 18:07

Since $g=(d_1,d_2)$ we have $g=rd_1+sd_2$ for some integers $r$, $s$. The general expression for $g$ is $g=(r+td_2/g)d_1+(s-td_1/g)d_2$, where $t$ is arbitrary.

From $m\equiv n\pmod g$ we get $$m=n+gk=n+k((r+td_2/g)d_1+(s-td_1/g)d_2)$$ for some integer $k$. We want to know if we can choose $t$ so that $$(n+k(r+td_2/g)d_1,q)=1$$ To put it another way, this is $(u+tv,q)=1$, where $u=n+krd_1$ and $v=kd_1d_2/g$.

This will be impossible if there is a prime $p$ which divides $u$, $v$, and $q$, that is, a prime dividing $n+krd_1$, $kd_1d_2/g$, and $q$. Such a prime can't divide $k$ or $d_1$, since $(n,q)=1$, but I don't see how to rule out the possibility that it divides $n+krd_1$, $d_2/g$, and $q$.

If we can rule out that possibility, then we can proceed: let $t$ be the product of all the primes that divide $q$ but not $u$. Then any prime dividing $q$ divides either $u$ or $tv$, but not both, hence, not $u+tv$, and we're done.

share|cite|improve this answer

Let $q=q_1q_2$ where $q_1\mid(d_1d_2)^\infty$ and $(q_2,d_1d_2)=1$. Fix $a',b'\in\mathbb{Z}$ such that $m=n+a'd_1+b'd_2$, then for any $k\in\mathbb{Z}$ the pair $a=a'+kd_2$ and $b=b'-kd_1$ satisfies $m=n+ad_1+bd_2$. By $(q_2,d_1d_2)=1$ we can choose $k\in\mathbb{Z}$ such that $n+ad_1=n+a'd_1+kd_1d_2$ is congruent to $1$ mod $q_2$, in particular $(n+ad_1,q_2)=1$. We claim that we also have $(n+ad_1,q_1)=1$. Indeed, let $p$ be a prime dividing both $n+ad_1=m-bd_2$ and $q_1$. Note that $p\nmid mn$ by $(mn,q)=1$. Note also that either $p\mid d_1$ or $p\mid d_2$. In the first case $p\nmid n+ad_1$, a contradiction. In the second case $p\nmid m-bd_2$, a contradiction. Finally $(n+ad_1,q_2)=1$ and $(n+ad_1,q_1)=1$ imply that $(n+ad_1,q)=1$. The proof is complete.

share|cite|improve this answer

Your Answer


