Primes $p$ with $\mathrm{ord}_p(z)\equiv a\pmod d$ Suppose that $a$, $z$, and $d\ge 2$ are integer numbers such that $z$ is not a perfect power; in particular, $z\notin\{0,\pm1\}$. What can be said about the existence / infinitude of the primes $p\equiv 1\pmod d$ such that $\mathrm{ord}_p(z)\equiv a\pmod d$? Such that $\mathrm{ord}_p(z)\not\equiv a\pmod d$?
At least, do there exist / are there infinitely many primes $p\equiv1\pmod d$ with $\mathrm{ord}_p(z)$ divisible / not divisible by $d$?
I suspect that algebraic number theory can be relevant, but if possible, I would prefer to have an elementary solution.
 A: It's not the most elementary answer but at least it's an answer... 
Consider the sequence:
$$a_n=z^n-1$$
Zsigmondy theorem assures that (with minor exceptions) each number in this sequence has a prime divisor $p_n$ which does not divide any previous terms. That is we have:
$$z^n \equiv 1\pmod{p_n}$$
And:
$$z^k \not \equiv 1 \pmod{p_n}$$
For all $1 \le k <n$. So by definition of the order we must have:
$$ord_{p_n}(z)=n$$
So for each $n$ (again, with minor exceptions) there exist such prime that $z$ has this order modulo this prime which is much stronger than both your assertion as well as its negation.  
Also note that the weaker version (infinitude of primes such that $p\equiv 1\pmod d$ or $p \not \equiv1\pmod d$) follows directly from the Dirichlet theorem on arithmetic progressions (which is also not quite elementary result).
A: $$z=dx+b\\y=dc+a\\p=de+1\\f=pg+1\\z^y=f\implies b^{dc+a}\equiv g+1\bmod d$$
if d was prime, this would lead to :$$b^{c+a}\equiv g+1\bmod d$$
In the d is composite ( and in general) case, this just replaces c with $$(d-\varphi(d))c$$ 
That's how far I got so far.
