0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – J. W. Tanner May 6 at 16:58
  • $\begingroup$ 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$. $\endgroup$ – Mike May 7 at 17:17
  • $\begingroup$ I just edited the problem. I hope that helped to clarify $\endgroup$ – joseph May 7 at 17:30
2
$\begingroup$

\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}$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I think you mean $a^t$ where you wrote $a^N$ $\endgroup$ – J. W. Tanner May 6 at 17:05
  • $\begingroup$ 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$? $\endgroup$ – joseph May 6 at 17:10
  • $\begingroup$ 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)^*$? $\endgroup$ – joseph May 7 at 15:39
  • $\begingroup$ 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$? $\endgroup$ – Mike May 7 at 17:13
  • $\begingroup$ I am confused as to what you mean by that notation. $\endgroup$ – joseph May 7 at 17:35

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.