Why Does Modulus Primality Matter in Congruences?

[evinda]

Hey! (Smile)

Is it known that if $p,q$ primes with $p \neq q$ :

$$a^p \equiv a \pmod q \Rightarrow a^{p \cdot q} \equiv a^q \pmod q$$
?
If so,why is it like that? Which property is used?

 

[I like Serena]

Hey! (Smile)

Is it known that if $p,q$ primes with $p \neq q$ :

$$a^p \equiv a \pmod q \Rightarrow a^{p \cdot q} \equiv a^q \pmod q$$
?
If so,why is it like that? Which property is used?

Hi! (Happy)

If $A \equiv B \pmod{n}$ then $A^m \equiv B^m \pmod{n}$.

Can you verify the validity of this property? (Wondering)

 

[evinda]

Hi! (Happy)

If $A \equiv B \pmod{n}$ then $A^m \equiv B^m \pmod{n}$.

Can you verify the validity of this property? (Wondering)

We could prove it by induction,right?

• $m=0: A^0=1, B^0=1, \text{ so,we have } 1 \equiv 1 \pmod{n} \checkmark $
• Suppose that the relation is true,for $m=k$.So,we have $A^k \equiv B^k \pmod{n}$
• for $m=k+1$: $A^{k+1} \equiv A^k \cdot A \equiv B^k \cdot B \equiv B^{k+1} \pmod{n}$

So,we conclude that if $A \equiv B \pmod{n}$ then $A^m \equiv B^m \pmod{n}$, $\forall m \in \mathbb{N}$... (Blush)

 

[I like Serena]

We could prove it by induction,right?

• $m=0: A^0=1, B^0=1, \text{ so,we have } 1 \equiv 1 \pmod{n} \checkmark $
• Suppose that the relation is true,for $m=k$.So,we have $A^k \equiv B^k \pmod{n}$
• for $m=k+1$: $A^{k+1} \equiv A^k \cdot A \equiv B^k \cdot B \equiv B^{k+1} \pmod{n}$

So,we conclude that if $A \equiv B \pmod{n}$ then $A^m \equiv B^m \pmod{n}$, $\forall m \in \mathbb{N}$... (Blush)

Looks good. ;)

You are using the property that $A \equiv B \pmod{n} \Rightarrow CA \equiv CB \pmod{n}$ though.
Can you verify the validity of that property? (Wondering)

 

[evinda]

Looks good. ;)

You are using the property that $A \equiv B \pmod{n} \Rightarrow CA \equiv CB \pmod{n}$ though.
Can you verify the validity of that property? (Wondering)

Where do you mean that I use this property?? (Worried)(Sweating)

We can show that $A \equiv B \pmod{n} \Rightarrow CA \equiv CB \pmod{n}$,like that:

$$A \equiv B \pmod{n}, \text{ that means that } n \mid A-B \Rightarrow n \mid C(A-B) \Rightarrow n \mid CA-CB \Rightarrow \\ \Rightarrow CA \equiv CB \pmod{n}$$ (Nerd)

 

[I like Serena]

Where do you mean that I use this property?? (Worried)(Sweating)

You conclude from $A^k \equiv B^k$ that $A^k\cdot A \equiv B^k\cdot B \pmod n$.

Hmm... so actually you are using that if $A\equiv B\pmod{n}$ and $C\equiv D\pmod{n}$, that then $AC\equiv BD\pmod{n}$. (Worried)

We can show that $A \equiv B \pmod{n} \Rightarrow CA \equiv CB \pmod{n}$,like that:

$$A \equiv B \pmod{n}, \text{ that means that } n \mid A-B \Rightarrow n \mid C(A-B) \Rightarrow n \mid CA-CB \Rightarrow \\ \Rightarrow CA \equiv CB \pmod{n}$$ (Nerd)

Good! (Sun)

 

[Deveno]

Hi! (Happy)

If $A \equiv B \pmod{n}$ then $A^m \equiv B^m \pmod{n}$.

Can you verify the validity of this property? (Wondering)

See, I've always found this view of things cumbersome.

Once one establishes that "congruence mod $n$" IS a (ring) congruence, we can drop the annoying (mod $n$) in parentheses afterwards, and just do arithmetic like we're used to. If we need to emphasize that we're not using "ordinary integers", we can indicate this with vincula or brackets.

So if $[a] = $, then:

$[a^m] = [a]^m = ^m = [b^m]$. You don't even need induction.

In my mind, trying to explicitly tie everything back to properties of the integers, defeats the entire purpose of working "mod $n$" which is to reduce an infinitude of possibilities to a finite number of cases.

The map $a \mapsto [a]_n$ is a surjective ring homomorphism: $\Bbb Z \to \Bbb Z_n$. In the latter ring, we replace "congruent mod $n$" with EQUALITY, and are thus working with EQUATIONS. I prefer equations over equivalences.

The idea is: instead of thinking about the NUMBER $n$, we think about the IDEAL $(n)$. This is going to (even for number theory) generalize much better to other number systems: prime factorization (of numbers) may break down, but factorization into prime ideals is more robust.

 

[evinda]

See, I've always found this view of things cumbersome.

Once one establishes that "congruence mod $n$" IS a (ring) congruence, we can drop the annoying (mod $n$) in parentheses afterwards, and just do arithmetic like we're used to. If we need to emphasize that we're not using "ordinary integers", we can indicate this with vincula or brackets.

So if $[a] = $, then:

$[a^m] = [a]^m = ^m = [b^m]$. You don't even need induction.

In my mind, trying to explicitly tie everything back to properties of the integers, defeats the entire purpose of working "mod $n$" which is to reduce an infinitude of possibilities to a finite number of cases.

The map $a \mapsto [a]_n$ is a surjective ring homomorphism: $\Bbb Z \to \Bbb Z_n$. In the latter ring, we replace "congruent mod $n$" with EQUALITY, and are thus working with EQUATIONS. I prefer equations over equivalences.

The idea is: instead of thinking about the NUMBER $n$, we think about the IDEAL $(n)$. This is going to (even for number theory) generalize much better to other number systems: prime factorization (of numbers) may break down, but factorization into prime ideals is more robust.

I understand...thank you! (Smile)

 

[I like Serena]

So if $[a] = $, then:

$[a^m] = [a]^m = ^m = [b^m]$. You don't even need induction.

The map $a \mapsto [a]_n$ is a surjective ring homomorphism: $\Bbb Z \to \Bbb Z_n$. In the latter ring, we replace "congruent mod $n$" with EQUALITY, and are thus working with EQUATIONS. I prefer equations over equivalences.

How about the distinction between a ring and a field?
For instance, when we write $x \equiv 11 \pmod{341}$ or $x \equiv 11 \pmod{347}$, it is not clear whether we will have an inverse or not. If we know that $n$ is prime, this is immediately clear.

So it would be nice if we could somehow indicate this in the notation.
I'm not aware of any such notation though, other than writing for instance the cumbersome
$$x \equiv 11 \pmod{347} \quad \text{ where 347 is prime}$$
which contains the implication that we're talking about a field.

 

[Deveno]

How about the distinction between a ring and a field?
For instance, when we write $x \equiv 11 \pmod{341}$ or $x \equiv 11 \pmod{347}$, it is not clear whether we will have an inverse or not. If we know that $n$ is prime, this is immediately clear.

So it would be nice if we could somehow indicate this in the notation.
I'm not aware of any such notation though, other than writing for instance the cumbersome
$$x \equiv 11 \pmod{347} \quad \text{ where 347 is prime}$$
which contains the implication that we're talking about a field.

We don't have to know the modulus is prime, we have to know the element we're trying to invert is co-prime to the modulus.

Sometimes, it's helpful to "tag" the modulus (Wikipedia does this in its article on the Chinese Remainder Theorem, where we deal with simultaneous congruences of different moduli). So you might want to write:

$[a]_{13}$ for example, or if the prime is not known:

$[a]_p$, where $p$ is prime.

My point isn't about properties of the modulus itself (primes are obviously special; we have, for example Fermat's Little Theorem, instead of the less-comprehensive Euler's Theorem which requires restrictions on the relationship between $[a]_n$ and $n$ itself), it's about trying to take everything back to things like:

$a \equiv m \text{ (mod }n) \implies a = m + kn$ <---already we have some spurious integer $k$ which we don't need.

All of this is already coded in $[a]_n = [m]_n$, and we can work with the equivalence classes DIRECTLY. This is similar to what is done with field extensions:

formally, $\Bbb C = \Bbb R[x]/\langle x^2 + 1\rangle$, but nobody works with complex numbers "carrying around the principal ideal generated by $x^2 + 1$". We give the coset of $x$ a name ($i$ or $j$), and just deal with $a + bi$.

When I actually do calculations mod 5, for example, I will do stuff like:

3x + 4 = 2
3x = 3 (add 1 to both sides)
x = 1 (multiply both side by 2)

If I was working mod 12, I would start:

3x + 4 = 2
3x = 10 (add 8 to both sides)
0 = 4 (multiply by 4: contradiction, no solution).

I don't even have to know ahead of time if an element is invertible, I can find out by looking at gcd's.

Yes, not all moduli are equally "nice" (not all integers are equally "nice"), but the arithmetic still works (sure, not all finite cyclic rings are fields: the integers aren't a field either. Sure, some cyclic rings have zero-divisors, some integers are highly divisible).

We lose some information when we consider the integers modulo (something). We also gain something: we have less information to wade through. If the information we lost wasn't relevant, we can make progress on our original problem.

Sure, the $n$ in $\Bbb Z \to \Bbb Z_n$ MATTERS, it's the characteristic in our new ring. Rings of different characterstic have (dare I say this?) different characteristics. But they're still rings, and everything we do is still "kosher" (except division-this is sort of a "special case", diving by zero isn't allowed in ANY structure, and zero-divisors act much like zero, they're "bad").

My vaguely-defined strategy for problem-solving: simplify the problem to something "smaller", play in the small sandbox until what I want to show is trivial: blow it back up.

When working with problems involving integers: often one uses prime factorization to consider prime or co-prime cases, and then use these "special cases" to (hopefully) recover the "general case". Sometimes this works, sometimes it doesn't. Some problems (like Goldbach's conjecture) are really HARD.

I believe if Euler or Gauss were alive today, they would happily adapt to a more modern point of view: algebra was in its infancy at those times, and they did the best they could with the tools available.