Calculating ${34}^{429} \mod 431$

Question

I am trying to calculate $${34}^{429} \mod 431$$ by hand. (This follows from $34^{-1}\mod 431$).

I think I have made mistakes in my working, and have three different answers thus far from the attempts:

$$351, 306, 134$$

Is one of these correct? If none of the above is correct please provide an answer with working.

Answer 1

You can use the extended Euclidean algorithm to find the inverse of $34\bmod 431$:

$\begin{array}{c|c} n & s & t & q \\ \hline 431 & 1 & 0 & \\ 34 & 0 & 1 & 12 \\ 23 & 1 & -12 & 1 \\ 11 & -1 & 13 & 2 \\ 1 & 3 & -38 & 11 \\ \end{array}$

... with each line expressing $n=431s+34t$ by suitable combination of the previous two lines.

The final line gives $3\cdot 431 + (-38)\cdot 34 = 1$, so $(-38)\cdot 34\equiv 1 \bmod 431$ and thus $34^{-1}\equiv -38\equiv 393 \bmod 431$

Answer 2

$$431=34(12)+23$$ $$34=23+11$$ $$23=2(11)+1$$

Hence

\begin{align}1&=23-2(11) \\ &=23-2(34-23)\\ &=3(23)-2(34)\\ &=3(431-34(12))-2(34)\\ &=3(431)-38(34)\end{align}

Hence $$(-38)(34) \equiv 1 \mod 431$$

$$431-38=393$$

Answer 3

$$431=12\cdot 34+23$$ $$34=23\cdot 1+11$$ $$23=2\cdot11+1$$ And now, $$1=23-2\cdot 11=23-2\cdot(34-23\cdot 1)=23\cdot3-34\cdot2=$$ $$=(431-12\cdot34)\cdot 3-34\cdot 2=431\cdot 3-38\cdot 34$$

Answer 4

One can see that $\lceil\dfrac{431}{34}\rceil=13$;

$$13.34\overset{431}{\equiv}11;$$

again, one can see that $\lfloor\dfrac{431}{11}\rfloor=39$;

$$39.11\overset{431}{\equiv}-2;$$

finally one can see easilly that:

$$(-216).(-2)\overset{431}{\equiv}1.$$

---

So we have:

$$(-216)\Bigg(39\big(13.34\big) \Bigg) \overset{431}{\equiv} (-216)\Bigg(39\big(11\big) \Bigg) \overset{431}{\equiv} (-216)\Bigg(-2 \Bigg) \overset{431}{\equiv} 1;$$

so we can conclude that:

$$34^{-1} \overset{431}{\equiv} (-216).39.13 \overset{431}{\equiv} 393.$$

Answer 5

$\bmod 431\!:\ \color{#c00}{\dfrac{1}{34}}\equiv \color{#0a0}{-38}\equiv 393\,$ by $2$ steps of the Extended Euclidean algorithm in fraction form

$$\dfrac{0}{431}\, \overset{\large\frown}\equiv\!\! \underbrace{\color{#c00}{\dfrac{1}{34}}\ \overset{\large\frown}\equiv \color{#90f}{\dfrac{-13}{-11}}\ \overset{\large\frown}\equiv\ \color{#0a0}{\dfrac{-38}{1}}} _{\,\Large \begin{align}\color{#c00}{1}\ \ + \ \ &3(\color{#90f}{ -13 }) \ \ \ \equiv \ \ \color{#0a0}{-38}\\ \color{#c00}{34}\ \ +\ \ &3(\color{#90f}{-11} )\ \ \ \equiv\ \ \ \ \color{#0a0}{1}\ \ \ \end{align}}\qquad\qquad $$

---

Alternatively we can apply Gauss's inversion algorithm in fractional form

$$\bmod{431}\!:\,\ \dfrac{1}{\color{#0a0}{34}}\equiv \dfrac{\color{#c00}{13}\cdot 1\ }{\color{#c00}{13}\cdot34}\equiv\dfrac{13}{\color{#0a0}{11}}\equiv\dfrac{\color{#c00}{39}\cdot(11\!+\!2)}{\color{#c00}{39}\cdot 11\qquad}\equiv\dfrac{-2+2\cdot 39}{\color{#0a0}{-2}}\equiv -38 $$ i.e. iteratively reduce the $\rm\color{#0a0}{denominators}$ by $\rm\color{#c00}{scalings}$ till it divides the numerator. This is precisely what is done in Famke's answer (but replacing fractions $\,x\equiv a/b\,$ by equations $\,b\,x\equiv a)$

Answer 6

$$34^{429}=\left(\big(\big(34)^{13}\big)^{11}\right)^3$$ Then in $\mathbb F_{431}$ we have $$34^{13}=34^8\cdot34^5=373\\373^{11}=373^6\cdot373^5=420\\420^3=\color{red}{393}$$

Answer 7

Ignoring the fact that we're looking for the inverse, I'll lay out the exponentiation-by-squaring answer to getting $34^{429}\bmod 431$, for reference.

The process is to square a running product repeatedly, interspersed by multiplying by $34$ as required, taking numbers $\bmod 431$ throughout the process. The idea is that we build up the exponent of our running product by factors of two until reaching the target exponent of $429$.

Perhaps the easiest way to relate to this process is to look at the binary representation of the exponent, $429_{dec} = 110101101_{bin}$ We will increase the exponent by taking successively more from the left hand side of this binary representation, $1\to 3\to 6\to 13 \to 26\to 53\to 107 \to 214 \to 429$, either squaring alone for a simple doubled exponent or square-and-multiply to get to the odd exponents.

\begin{array}{c|c} \to exp & prev & prev^2 & [\times 34] \\ \hline 1 & 1 & 1 & 34 \\ 3 & 34 & 294 & 83 \\ 6 & 83 & 424 & - \\ 13 & 424 & 49 & 373 \\ 26 & 373 & 347 & - \\ 53 & 347 & 160 & 268 \\ 107 & 268 & 278 & 401 \\ 214 & 401 & 38 & - \\ 429 & 38 & 151 & \color{red}{393} \\ \end{array}

The requires handling numbers potentially up to $430^2$ (and then taking modulo $431$). By judicious use of negative values the limit could be brought down to $215^2$ (for example, $34^6\equiv 424 \equiv -7$ so $34^{12}\equiv -7^2\equiv 49$). A simple calculator was sufficient here to complete the tableau.