1
$\begingroup$

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.

Kuzma

$\endgroup$
1
  • $\begingroup$ I just realized this is Exercise 1(a) from Section 9.1.1 in Montgomery-Vaughan: Multiplicative Number Theory I. $\endgroup$
    – GH from MO
    Feb 28, 2016 at 18:07

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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