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

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.

• What method are you using? Successive squaring or something else? – Michael Burr Aug 21 '17 at 19:56
• You can multiply them all by $34$ to see if either of them are $34^{-1}$. – Arthur Aug 21 '17 at 19:56
• This is equivalent to solving for $x$ in $1 = 34x + 431y$ which you can compute using Euclid's Algorithm. Hope this helps. – 伽罗瓦 Aug 21 '17 at 20:00
• @michaelburr I used a slightly different route on each attempt. For third attempt I only used powers of 34 and reduced mod 431 each time. For first and second attempts I broke multiplication down in different ways and used the results & raised the results to powers & simplified. – unseen_rider Aug 21 '17 at 20:02
• @arthur I don't see how that would help since I don't know what $34^{-1}$ is? – unseen_rider Aug 21 '17 at 20:07

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$

• It's easier (2 steps) using signed remainders and fractions - see my answer. – Bill Dubuque Aug 21 '17 at 20:52
• @BillDubuque Yours is fewer steps, certainly, but I'll leave the decision on which is easier to the interested reader. Also, this is only three steps, really, since the first two lines are just tableau setup. – Joffan Aug 21 '17 at 21:07

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

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

• It seems you omitted many (painful!) calculations. Euclid's algorithm is much easier - a few single digit calculations except for the first step $\,431 - 13(\color{#c00}{34}) = \color{#90f}{-11}\$ – Bill Dubuque Aug 21 '17 at 22:27
• I wanted to give a different way to solve. (However it is not so different in nature....). – Piquito Aug 21 '17 at 22:52

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.

$\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)$

• I'm curious as to why $\frac{-13}{-11}$ (negative #s) and not just $\frac{13}{11}$ (from $\frac{13}{442}$) – Joffan Aug 21 '17 at 21:10
• @joffan The prior step was \begin{align} 0 - 13(\color{#c00}1)\ \ \,&=\,\color{#90f}{-13}\\ 431 - 13(\color{#c00}{34}) \,&\,= \color{#90f}{-11}\end{align}\ We could of course cancel $\,{-}1\$. – Bill Dubuque Aug 21 '17 at 22:06
• Joffan We are doing the Euclidean algorithm on the denominators using remainders of least magnitude, for eaxample above we have $\ \ 431\,\bmod\ \color{#c00}{ 34}\ =\ \color{#90f}{{-}11}\,$ with quotient $13\ \$ – Bill Dubuque Aug 21 '17 at 22:11
• Ok, thanks for the explanation. – Joffan Aug 21 '17 at 22:12

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

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

• As I note in my answer, this is precisely Gauss's inversion algorithm, which is clearer in fractional form, viz. $$\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. – Bill Dubuque Aug 22 '17 at 15:11
• What are scalings? – unseen_rider Aug 24 '17 at 5:40