Exercise 2.4.10 (Method of factorization)

Question

Note that $85 = (341 - 1)/4$. Show that $2^{85} \equiv 32 
ot \equiv \pm 1 \pmod{341}$, and that $2^{170} \equiv 1 \pmod{341}$. Deduce that $341$ is a pseudoprime base $2$, but not a spsp($2$). Apply the Euclidean algorithm to calculate $(32 \pm 1,341)$, and thus find numbers $d,e,\ 1<d<341$, such that $de = 341$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

\begin{proof}

For $m = 341$, the two congruences
$$ 2^{(m-1)/4} = 2^{85} \equiv 32 \pmod m,\qquad 2^{(m-1)/2} \equiv 1 \pmod m,$$
show that $341$ is not a spsp($2$).

Moreover
$2^{m-1} = \left( 2^{(m-1)/2}ight)^2 \equiv 1 \pmod m$, so $m$ is a pseudoprime to the base $2$.

By Problem 11, since $  x^2\equiv 1 \pmod m$ and $x 
ot \equiv \pm 1 \pmod m$, where $x = 2^{(m-1)/4}$, then $(x-1)\wedge m$ and $(x+1) \wedge m$ are non trivial divisors of $m$.

Since $x = 32 + km,\ k \in \Z$, $(32 \pm 1) \wedge m = (x \pm 1 \wedge m$  are non trivial divisors of $m$.

Then $33 \wedge 341 = 11$ and $31 \wedge 341 = 31$ are divisors of $m = 341$. This gives the factorization
$$341 = 11 	imes 31.$$

\end{proof}

Exercise 2.4.10 (Method of factorization)

Answers

Comments

Exercise 2.4.10 (Method of factorization)

Answers

Comments

Add answer