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?
 A: 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$.   

A: 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.
