# Prove $a^t$ is congruent to $1$ modulo one of the primes $p,q$ and $-1$ modulo the other prime.

Let $$p$$ and $$q$$ be odd primes, and let $$N=pq$$. Let $$t$$ be a positive integer such that $$a^{2t}\equiv1\pmod{N}$$ for all $$a\ \epsilon\ (\mathbb Z/N\mathbb Z)^*$$, but the congruence $$a^t\equiv1\pmod{N}$$ does not hold for all $$a\ \epsilon\ (\mathbb Z/N\mathbb Z)^*$$

I was able to show that thus either $$p-1\not|t$$ or $$q-1\not|t$$. I am now trying to show that for $$50$$% of the $$a\ \epsilon\ (\mathbb Z/N\mathbb Z)^*$$, $$a^t$$ is congruent to $$1$$ mod one the primes $$p,q$$ and $$-1$$ the other prime.

EDIT: Using the work done from before I now have.. We consider this in two cases: the first when exactly one $$p-1$$ or $$q-1$$ divides $$t$$, the second when neither divide $$t$$. In the first case, since $$(p-1)|t$$, we have that $$a^t\equiv1\pmod{p}$$. We also have that $$a^{2t}\equiv1\pmod{pq}$$ which implies that $$(a^t+1)(a^t-1)\equiv0\pmod{q}$$. And since $$a^t\not\equiv1\pmod{pq}$$, $$a^t\not\equiv1\pmod{q}$$. Therefore $$a^t\equiv-1\pmod{q}$$. So every time either $$p-1$$ or $$q-1$$ divides $$t$$ we have that $$a^t$$ is congruent to $$1$$ modulo one prime and $$-1$$ modulo the other prime. In the other case, it is my understanding that we would have both congruent to $$-1$$ so that case would give us zero ouputs we want. I still don't quite understand how this accounts for $$50$$% of the reqults.

• If $N=pq\;$ divides $a^{2t}-1$ then $p$ and $q$ divide $(a^t-1)(a^t+1)$ so $p$ divides $a^t-1$ or $a^t+1$ and same with $q$ – J. W. Tanner May 6 '19 at 16:58
• I am confused by this question as written. But what about $a=1$? Then $a^t \equiv 1$ mod $N$ for every positive integer $t$. – Mike May 7 '19 at 17:17
• I just edited the problem. I hope that helped to clarify – joseph May 7 '19 at 17:30

\begin{align*} a^{2t} & \equiv 1 \pmod{N} & \iff && (a^t-1)(a^t+1) \equiv 0 \pmod{p}\\ & & && (a^t-1)(a^t+1) \equiv 0 \pmod{q} \end{align*} Using the prime property: $$p \mid ab \implies p \mid a \text{ or } p \mid b$$. We get \begin{align*} a^ t & \equiv \pm 1 \pmod{p}\\ a^ t & \equiv \pm 1 \pmod{q} \end{align*} This gives you 4 possibilities. But one of the possibilities: $$a^t \equiv 1 \pmod{p}$$ and $$a^t \equiv 1 \pmod{q}$$ is NOT viable because we are given $$a^t \not\equiv 1 \pmod{N}$$.
• I think you mean $a^t$ where you wrote $a^N$ – J. W. Tanner May 6 '19 at 17:05
• Very helpful thank you. How would I show that this accounts for $50$% of the $a$ in the domain? Or do I need to show this is also true for some $a$ of the case where neither $p-1$ nor $q-1$ divides $t$? – joseph May 6 '19 at 17:10
• I am still confused as to how I proceed from here. It seems to me as if we then have that in the case $p-1|t$, then $a^t\equiv1\pmod{p}$. Thus, $a^t\equiv -1\pmod{q}$ since they can't both be congruent to $1$. In the case where $q-1|t$ we have the opposite. But when neither divide $t$, then both congruences are $-1$. If that's true, then how is this supposed to hold for $50$% of the elements in $(\mathbb Z/N\mathbb Z)^*$? – joseph May 7 '19 at 15:39
• More needs to be done here, I think. Why not $a_t \equiv_q -1 \equiv_p a^t$ e.g., $N|a^t+1$? – Mike May 7 '19 at 17:13