# If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then...

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?

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$.
• Good! your argument is neater than mine. I'll leave mine up as a cautionary tale for others.
– lulu
Jul 10 '15 at 23:39
• Thanks. I think your approach adds something. I certainly would leave it up.
– quid
Jul 10 '15 at 23:40
• 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? Jul 11 '15 at 13:49
• I expanded the post.
– quid
Jul 11 '15 at 16:59

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.

• Counterexample: $a=3$ and $m =6$.
– quid
Jul 10 '15 at 23:18
• Ah, good point. I will take down my answer until I can correct my error (whatever it may be!)
– lulu
Jul 10 '15 at 23:24
• @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?
– lulu
Jul 10 '15 at 23:33
• Yes, I agree. I was working on my own answer in parallel.
– quid
Jul 10 '15 at 23:38