Obtener el módulo de la $\phi(pqr)$ sin calculadora

Question

Dadas $p, q, r$ son números primos y $n = pqr = 398585546147$, ¿Cómo obtengo $\phi(pqr) \bmod 32$?

He intentado equiparar a $(p - 1)(q - 1)(r - 1) \bmod 32$ pero no sé cómo proceder desde allí. Calculadoras no están permitidas para esta pregunta así.

Answer 1

Respuesta parcial . . .

Aunque no se especifica explícitamente, yo sospecho que era la intención de que los números primos $p,q,r$ son distintos. Por lo tanto, en lo que sigue, voy a asumir la $p,q,r$ son distintos.

Como usted señaló, $n = pqr \implies \phi(n) = (p-1)(q-1)(r-1)$.

\begin{align*} n \text{ odd}&\implies p,q,r \text{ are odd }\\[6pt] &\implies p-1,q-1,r-1 \text{ are even}\\[6pt] &\implies 8\,|\,(p-1)(q-1)(r-1)\\[6pt] &\implies \phi(n) \equiv 0 \pmod 8\\[6pt] \end{align*}

Desde $n \equiv 3 \pmod 4$,

• Caso $(1)\;\;$Exactamente uno de $p,q,r$ es congruente a $3$ mod $4$, y los dos restantes son congruentes a $1$ mod $4$.
• Caso $(2)\;\;p,q,r$ son todos congruentes a $3$ mod $4$.

Para el caso de $(1)$, dos de $p-1,q-1,r-1$ son múltiplos de $4$, y el restante incluso uno de ellos es, por tanto,$\phi(n)=0 \pmod{32}$.

Para el caso de $(2)$, cada una de las $p-1,q-1,r-1$ es aún, pero no es un múltiplo de a $4$. De ello se desprende que $\phi(n)$ es un múltiplo de a $8$, pero no es un múltiplo de a $16$, por lo tanto $\phi(n) = 8 \text{ or }24 \pmod{32}$.

Por lo tanto, $\phi(n)\text{ mod }32$ es uno de $0,8,24$.