Add Me!Close Menu Navigation

Power Reduction in Congruences

Suppose you have integers a,b that are relatively prime to m such that

    $$ a^x \equiv b^x \mod m \hspace{4mm}\mbox{ and }\hspace{4mm} a^y \equiv b^y \mod m $$

then

    $$ a^{\gcd(x,y)} \equiv b^{\gcd(x,y)} \mod m $$

We first prove a useful lemma in working with algebraic manipulations in modular arithmetic.

1. Lemma: ac \equiv bc \mod m \implies a \equiv b \mod \frac{m}{\gcd(c,m)}

Here, we take the traditional definition that ac \equiv bc \mod m \iff m|(ac-bc).

    \begin{align*} ac \equiv bc \mod m &\implies m|(ac-bc) \\ &\implies m|c(a-b) \\ \intertext{if $(m,c)=1$, then $m|(a-b)$, but if $(m,c)=d \ne 1$, then $\frac{m}{d}|(a-b)$. \blacksquare} \end{align*}

2. Show that a^{(x,y)} \equiv b^{(x,y)} \mod m

By construction of the \gcd(x,y), we know that \gcd(x,y) = ux-vy. It follow that

    \begin{align*} a^{ux} \mod m &= (a^x \mod m)^u \mod m \\ &= (b^2 \mod m)^u \mod m \\ & \implies a^{ux} \equiv b^{ux} \mod m \\ & a^{vy} \equiv b^{vy} \mod m \end{align*}

The last two lines of the above gives another congruence expression:

    \[a^{ux}b^{vy} \equiv a^{vy}b^{ux} \mod m\]

Suppose that vy < ux as (x,y) = ux-vy must be positive. Because a,b are both relatively prime to m, then by the above lemma, we know that

    \[a^{ux}b^{vy} \equiv a^{vy}b^{ux} \mod m \implies \frac{a^{ux}b^{vy}}{b^{vy}} \equiv \frac{a^{vy}b^{ux}}{b^{vy}} \mod \frac{m}{\gcd(m,b^{vy})=1}\]

Likewise, we can divide a^{vy} out from both sides

    \[a^{ux} \equiv a^{vy}b^{ux-vy} \mod m \implies \frac{a^{ux}}{a^{vy}} \equiv \frac{a^{vy}b^{ux-vy}}{a^{vy}} \mod m\]

this gives us our final congruence equivalence

    \[a^{ux-vy} \equiv b^{ux-vy} \mod m\]

Because, ux-vy=\gcd(x,y), the above simplifies down to a^{\gcd(x,y)} \equiv b^{\gcd(x,y)} \mod m. \blacksquare

Alternatively

The same logic above can be used to justify that a^{|x-y|} \equiv b^{|x-y|} \mod m, therefore, you can also show inductively, on the steps of the euclidean algorithm, that it preserves the properties of congruence mod m.

Posted By Lee

Woosh

Recent Comments