# How do I verify if $2^{35} \equiv 1 \pmod{71}$ is true or not?

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.

• Are you familiar with Euler's criterion? – J. W. Tanner Nov 11 '20 at 17:04
• What about "by calculation" (even if you don't know more efficient methods, that would be 35 times multiplying by $2$ modulo $71$, come on...)? I mean, we were lazy students, then, but there were limits. – user436658 Nov 11 '20 at 17:08
• Further hint: $12^2\equiv 2 \bmod 71$ – Keith Backman Nov 11 '20 at 17:11
• On the topic of direct calculation, there are fast exponentiation algorithms such as Squaring. Just compute $2^{2^k} \pmod {71}$ for $k \le 5$. – player3236 Nov 11 '20 at 17:17
• Use \pmod{71} to get $\pmod{71}$ – Arturo Magidin Nov 11 '20 at 17:34

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

• $$\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$$ – 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$$.

• that's a simple answer ! (+1) – Spectre Nov 11 '20 at 17:20
• It works in this specific circumstance – J. W. Tanner Nov 11 '20 at 17:24
• Oh.. I see... Thanks for the information. – Spectre Nov 11 '20 at 17:51

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

• Should I be using $\equiv$ rather than = here? – Adam Rubinson Nov 11 '20 at 17:20
• I think the last $=$ should be $\equiv$ – Ekesh Kumar Nov 11 '20 at 17:21
• Thanks. Haven't done number theory since my Uni days... – Adam Rubinson Nov 11 '20 at 17:22
• $=$ 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. – Arthur Nov 11 '20 at 17:29
• That makes sense, Arthur. – Adam Rubinson Nov 11 '20 at 17:30

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

• You must have meant $35=7\color{red}1-36$ – J. W. Tanner Nov 11 '20 at 17:51
• @J.W.Tanner, yes, thank you. Fixed now. – Barry Cipra Nov 11 '20 at 18:05

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.

• You were closer at the start - see my comment on Neat's answer. – Bill Dubuque Nov 12 '20 at 5:31