Substitution in congruence relations

Question

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.

Answer 1

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.

Answer 2

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