2
$\begingroup$

Let $a,m\in \mathbb N$

Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m)

Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa?

I played around a bit with Dirichlet's theorem, but it did not help..

Can someone help me?

$\endgroup$
3
$\begingroup$

Note $n \equiv 1 \pmod{a}$ and $n \equiv 1 \pmod{m}$ is equivalent to $n \equiv 1 \pmod{\operatorname{lcm}(a,m)}$.

Thus you ask under which conditions almost all primes congruent $ 1 \pmod{a}$ are also congruent $1 \pmod{\operatorname{lcm}(a,m)}$.

Suppose $\operatorname{lcm}(a,m) = d a$. If there is some $1 \le k \le d-1$ such that $1 + ka$ is co-prime to $\operatorname{lcm}(a,m)$ then the class $1 + ka$ modulo $\operatorname{lcm}(a,m)$ contains infinitely many primes, that are $1 \pmod{a}$ yet not modulo $\operatorname{lcm}(a,m)$. Thus, the question boils down to deciding for which $a$ and $m$ such a $k$ cannot exist.

Now, we have the standard epimorphism $$ \begin{cases} \mathbb{Z}/da\mathbb{Z}^{\times} & \to \mathbb{Z}/a\mathbb{Z}^{\times} \\ n + da \mathbb{Z} & \mapsto n + a \mathbb{Z} \end{cases} $$

The kernel of this epimorphism are precisely the classes $1 +k a $ with $0 \le k \le d-1$ co-prime to $da$.

Thus, our condition can also be expressed as saying that the standard epimorphism from $\mathbb{Z}/da\mathbb{Z}^{\times}$ to $\mathbb{Z}/a\mathbb{Z}^{\times}$ is has kernel only $1 + da\mathbb{Z}$, that is it is injective.

However this means that the cardinalities of these two groups are the same, which are given by Euler's totient function, so $\varphi( da)= \varphi (a)$. Using the usual formula for the Euler totien function we see that this is only the case if $d=1$ or ($d=2$ and $a$ odd).

Thus, the characterization is:

  • $m$ divides $a$, or
  • $a$ is odd and $m$ divides $2a$.
$\endgroup$
4
  • $\begingroup$ Good! your argument is neater than mine. I'll leave mine up as a cautionary tale for others. $\endgroup$
    – lulu
    Jul 10 '15 at 23:39
  • $\begingroup$ Thanks. I think your approach adds something. I certainly would leave it up. $\endgroup$
    – quid
    Jul 10 '15 at 23:40
  • $\begingroup$ Hello. I dont understand the connection between the condition with the epimorphism and the things you wrote before. Can you make this clearer for me please? $\endgroup$ Jul 11 '15 at 13:49
  • $\begingroup$ I expanded the post. $\endgroup$
    – quid
    Jul 11 '15 at 16:59
2
$\begingroup$

Thanks to a commenter for finding a flaw in my first posted response. That earlier draft improperly handled the case where q (defined in the argument) is 2. As it stands, the argument only proves that $ord_q m ≤ ord_q a$ for every odd prime q.

To see this suppose, to the contrary, that $ord_q m > ord_q a$ for some odd prime q. Suppose, for illustration purposes, that q divides m but q does not divide a. Then, by Dirichlet, there exist infinitely many primes congruent to 1 mod a and congruent to 2 mod q. Those primes give a counterexample to your assumption. Similarly if $q^k$ divides m but only $q^i$ divides a, for 1 ≤ i < k, then we can still use Dirichlet to find infinitely many primes congruent to 1 mod a, but congruent to $(1+q^i)$ mod $q^k$. Again, these primes contradict your assumption.

$\endgroup$
4
  • $\begingroup$ Counterexample: $a=3$ and $m =6$. $\endgroup$
    – quid
    Jul 10 '15 at 23:18
  • $\begingroup$ Ah, good point. I will take down my answer until I can correct my error (whatever it may be!) $\endgroup$
    – lulu
    Jul 10 '15 at 23:24
  • $\begingroup$ @quid I believe the argument as it stands is still correct for odd primes q, no? Thanks for catching the error for q = 2. Can't believe 2 is that big a problem though....figure the only cases where m fails to divide a are when a is odd and m = 2a? $\endgroup$
    – lulu
    Jul 10 '15 at 23:33
  • $\begingroup$ Yes, I agree. I was working on my own answer in parallel. $\endgroup$
    – quid
    Jul 10 '15 at 23:38

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.