I need to know if $2^{35} \equiv 1\pmod{71}$ is true. I tried using Euler and Fermat little theorem and I got stuck. There is probably something trivial I'm not seeing so I appreciate any help, thanks.
Here's another way:
$$ 2^{36}\equiv 64^6 \equiv (-7)^6 \equiv (-343)^2 \equiv 12^2 \equiv 2 \pmod{71} \Rightarrow 2^{35} \equiv 1 \pmod{71} $$
-
1$\begingroup$ $$\large \text{Easier}\!:\ 1 \equiv 3^{\large 2} 2^{\large 3} \overset{\!\times\ 2}\Longrightarrow 2 \equiv (3\,2^{\large 2})^{\large 2}\overset{(\ \ )^{\Large 35}\!\!}\Longrightarrow\, 2^{\large 35}\equiv (3\,2^{\large 2})^{\large 70}\equiv 1\ \ \text{by little Fermat}\qquad\qquad$$ $\endgroup$ – Bill Dubuque Nov 12 '20 at 5:31
According to Euler's criterion, $2^{35}\equiv\left(\dfrac2{71}\right)\bmod71$.
Furthermore, $\left(\dfrac2{71}\right)=1$, because $71\equiv-1\bmod8$.
-
1
-
-
$$2^{35} = 2^{10} \times 2^{10} \times 2^{10} \times 2^5 \\ = 1024 \times 1024 \times 1024 \times 32 \\ \equiv 30 \times 30 \times 30 \times 32 \equiv 1 \mod 71.$$
-
$\begingroup$ Should I be using $\equiv$ rather than = here? $\endgroup$ – Adam Rubinson Nov 11 '20 at 17:20
-
-
$\begingroup$ Thanks. Haven't done number theory since my Uni days... $\endgroup$ – Adam Rubinson Nov 11 '20 at 17:22
-
$\begingroup$ $=$ should be used only when the number on either side of the symbol are actually equal, because that's what $=$ means. If you're doing any kind of modular reductions, you should use $\equiv$. You could use $\equiv$ everywhere, of course. $\endgroup$ – Arthur Nov 11 '20 at 17:29
-
Since $71\equiv3$ mod $4$, $k$ is a quadratic residue if and only if $71-k$ is a nonresidue. In particular, $70=71-1$ and $35=71-36$ are nonresidues. But since $70=2\cdot35$, we can conclude that $2$ is a quadratic residue, i.e., $2\equiv a^2$ mod $71$ for some $a$, in which case $2^{35}\equiv a^{70}\equiv1$ mod $71$ by Fermat's little theorem.
Remark: This approach shows that $2$ is the square of something without explicitly finding what it's the square of. In fact, as Keith Bachman points out in comments, $2\equiv12^2$ mod $71$.
-
$\begingroup$ You must have meant $35=7\color{red}1-36$ $\endgroup$ – J. W. Tanner Nov 11 '20 at 17:51
-
1
Using only 'ground floor' modular arithmetic theory, you can build a bottom-up presentation of exponent relations of the $\text{modulo-}71$ structure to answer this question.
To get things moving, you solve $2x = 1 \pmod{71}$ and find that $\large 2^{-1} = 2^2 \cdot 3^2 \pmod{71}$.
So,
$\quad 2^{35} \equiv 1 \pmod{71} \; \text{ iff}$
$\quad 2^{34} \equiv 2^2 \cdot 3^2 \pmod{71} \; \text{ iff}$
$\quad 2^{32} \equiv 3^2 \pmod{71}$
Observing the exponent pattern (down $3$, up $2$), and since $3^4 = 2 \cdot 5 \pmod{71}$, we take $8$ 'pivot' steps and continue the calculations,
$\quad 2^{35} \equiv 1 \pmod{71} \; \text{ iff}$
$\quad 2^{11} \equiv 3^{16} \pmod{71}\; \text{ iff}$
$\quad 2^{11} \equiv 2^{4}\cdot 5^{4} \pmod{71}\; \text{ iff}$
$\quad 2^{7} \equiv 5^4 \pmod{71}\; \text{ iff}$
$\quad 128 \equiv 625 \pmod{71}\; \text{ iff}$
$\quad 128 \equiv -85 \pmod{71}\; \text{ iff}$
$\quad 213 \equiv 0 \pmod{71}$
We have verified that the statement $2^{35} \equiv 1 \pmod{71}$ is true.
-
$\begingroup$ You were closer at the start - see my comment on Neat's answer. $\endgroup$ – Bill Dubuque Nov 12 '20 at 5:31
\pmod{71}
to get $\pmod{71}$ $\endgroup$ – Arturo Magidin Nov 11 '20 at 17:34