0
$\begingroup$

I'm a noob to discrete math, and have a basic question for a sanity check. From studying basic modular arithmetic, the following are properties of congruences:

1) $a \equiv a \pmod{n}$

2) $a \equiv b \pmod{n} \implies b \equiv a \pmod{n} $

3) $a \equiv b \pmod{n}$ and $ b \equiv c \pmod{n} \implies a \equiv c \pmod{n}$

4) $a \equiv b \pmod{n} \implies a+c \equiv b+c \pmod{n}$

5) $a \equiv b \pmod{n} \implies ac \equiv bc \pmod{n}$

6) $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n} \implies a+c \implies b+d \pmod{n}$

7) $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n} \implies ac \equiv bd \pmod{n}$

Powers of integers are just multiplications. More formally, property 5 plus induction can be used to prove:

8) $a \equiv b \pmod{n} \implies a^k \equiv b^k \pmod{n}$ for any nonnegative integer $k$

In addition, there is a "cancellation" lemma that states that: if $p$ is prime $k$ is not a multiple of $p$ by Fermat's little theorem, then

9) $ak \equiv bk \pmod{p} \implies a \equiv b \pmod{p}$

Here's my question, looking at the proof of https://en.wikipedia.org/wiki/Euler%27s_criterion

If there exists integer $x$ such that $a \equiv x^2 \pmod{p}$, and $a$ is coprime to $p$, then

$a^{(p-1)/2} \equiv (x^2)^{(p-1)/2} \equiv x^{p-1} \equiv 1 $

My question is that I am confused about the substitution of $a$ with $x^2$. If $a=x^2$, then it's obvious we can make substitutions like this. But since in this case $a \equiv x^2$, I'm confused about when it's allowed to make substitutions in congruence relations? None of the properties of congruences 1-8 applies to "substitutions."

The closest I can come to "substitution" in congruence relations is: Suppose that:

A) $ab \equiv c \pmod{p}$, where $p$ is a prime

B) $d \equiv b \pmod{p}$, where $p$ is a prime

Then multiply A) and B) as in property 7, I get:

$adb \equiv bc \pmod{p}$

Now using the cancellation property for modulo a prime (property 9), I can cancel $b$ to get:

$ad \equiv c \pmod{p}$

which is as if I simply substituted $b$ from B) into A).

So, because property 9 only applies to modulo a prime, does my apparent substitution only work since A) and B) are modulo a prime?

Does it also mean the substitution of $a$ with $x^2$ in the Euler's criterion only valid since Euler's criterion is modulo a prime? Or, am I confused about "substitutions" somehow? I'm actually unsure if the substitution of $a$ with $x^2$ in Euler's criterion proof is actually a real substitution since we're substituting into an expression $a^{(p-1)/2}$ rather an congruence relation where $a^{(p-1)/2}$ is already congruent to some other expression.

$\endgroup$
1
  • 1
    $\begingroup$ The possibility of substitutions is not specific to congruences, it is a general property of mathematical logic. As to cancellation, you can cancel $b$ even if the modulus is not prime. The condition is that $b$ be coprime to the modulus, because in this case, $b$ has a modular inverse, by Bézout's theorem. $\endgroup$
    – Bernard
    Nov 21 '17 at 2:04
1
$\begingroup$

There is nothing wrong here: you are using property $8$ with $b=x^2$ and $k=\frac{p-1}{2}$, which is an integer since $p$ is an odd number.

$\endgroup$
0
$\begingroup$

If $a\equiv b \pmod c$ then for every $n\in \Bbb N$ we have $a^n\equiv b^n \pmod c.$ There are several ways to prove this.

Method 1. Use the Binomial Theoerem. If $a\equiv b\pmod c$ then $b=a+kc$ for some $k\in \Bbb Z$. So for $2\leq n\in \Bbb N$ we have $$-a^n+b^n=-a^n+(a+kc)^n=-a^n+\sum_{j=0}^na^{n-j}(kc)^j\binom {n}{j}=$$ $$=-a^n+a^n+c\sum_{j=1}^na^{n-j}k^jc^{j-1}\binom {n}{j}=c\sum_{j=1}^na^{n-j}k^jc^{j-1}\binom {n}{j}$$ which is an integer multiple of $c.$ So $\;-a^n+b^n\equiv 0\pmod p.$

Method 2. Use induction on $n\geq 2.$ First, by your Rule # (7) with $c=a$ and $d=b$ we have $a\equiv b\pmod c\implies a^2\equiv b^2\pmod c.$

Second, if $2\leq n\in \Bbb N$ and $a\equiv b\pmod c$ and $a^n\equiv b^n \pmod c$ then by Rule #(7) with $c=a^n$ and $d=b^n$ we have $$a^{n+1}\equiv ac\equiv bd\equiv b^{n+1} \pmod c.$$

$\endgroup$

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.