Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.