2
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Are you familiar with Euler's criterion? $\endgroup$ – J. W. Tanner Nov 11 '20 at 17:04
  • 2
    $\begingroup$ 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. $\endgroup$ – user436658 Nov 11 '20 at 17:08
  • 2
    $\begingroup$ Further hint: $12^2\equiv 2 \bmod 71$ $\endgroup$ – Keith Backman Nov 11 '20 at 17:11
  • 2
    $\begingroup$ 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$. $\endgroup$ – player3236 Nov 11 '20 at 17:17
  • 1
    $\begingroup$ Use \pmod{71} to get $\pmod{71}$ $\endgroup$ – Arturo Magidin Nov 11 '20 at 17:34
1
$\begingroup$

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

$\endgroup$
1
  • 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
3
$\begingroup$

According to Euler's criterion, $2^{35}\equiv\left(\dfrac2{71}\right)\bmod71$.

Furthermore, $\left(\dfrac2{71}\right)=1$, because $71\equiv-1\bmod8$.

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

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

$\endgroup$
7
  • $\begingroup$ Should I be using $\equiv$ rather than = here? $\endgroup$ – Adam Rubinson Nov 11 '20 at 17:20
  • $\begingroup$ I think the last $=$ should be $\equiv$ $\endgroup$ – Ekesh Kumar Nov 11 '20 at 17:21
  • $\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
  • $\begingroup$ That makes sense, Arthur. $\endgroup$ – Adam Rubinson Nov 11 '20 at 17:30
1
$\begingroup$

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

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

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.

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

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.