MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.