What theorems are available when using modulo arithmetic?

[jedishrfu]

I'm looking for theorems related to using modulo arithmetic.

As an example, if I apply a sequence of arithmetic operations to a given number to get an answer and then apply a modulo operation on the result to get a remainder in a given base. Wiil that be the same if I apply the modulo operation intermittently between the arithmetic operations?

For arithmetic operations, I'm referring to +,-,*, / only

Consider the case of ##5!## to be ##5*4*3*2*1+1 =121## and 121 mod 6 vwould yield 1

vs

5*4 = 20 --> 20 mod 6= 2
2*3 = 6 ==> 6 mod 6 = 0
0*2 = 0 ==> 0 mod 6 = 0
0*1 = 0 ==> 0 mod 6 = 0
0+1 = 1 ==> 1 mod 6 = 1

Intuitively, it seems the same but I'm looking for a definitive proof for arbitrary modulo base.

A counterexample would be good too.

 

[fresh_42]

Modulo (whatever) is a ring homomorphism ##\varphi ,## so ##\varphi (a\cdot b)=\varphi (a)\cdot \varphi (b)## and ##\varphi (a + b)=\varphi (a)+ \varphi (b).## That covers all cases.

You only have to keep in mind that in case "whatever" isn't a prime then ##\varphi (a\cdot b)=0## is possible even if ##a## and ##b## are not zero, so ##\varphi (a)^{-1}## does not exist in all cases.

 

[PeroK]

The general case follows by induction on the case of two numbers for each binary operation. Let's say we have numbers ##a, b##. Then, for example, we have:
$$(a + b) mod(n) = (a + b \ mod(n)) \ mod(n) = (a \ mod(n) + b \ mod(n)) \ mod(n)$$

 

[Mark44]

Consider the case of ##5!## to be ##5*4*3*2*1+1 =121## and 121 mod 6 vwould yield 1

Typo above?
You seem to be asking about ##5! + 1##, not "the case of ##5!##".

 

[fresh_42]

The title is a bit different than your actual question with the example.

That modulo is a ring homomorphism is the principle behind the example. Other theorems and tools in that area are the Chinese remainder theorem, Bézout's identity, Fermat's little theorem, Euler's totient function which is the central subject of RSA encryption (*), the law of quadratic reciprocity, Legendre symbols, Kronecker symbols, Zolotarev's lemma, and Euler's criterion.

(*) Shamir is a nice guy. I had the chance to have lunch with him in the early nineties.

 

[jedishrfu]

Typo above?
You seem to be asking about ##5! + 1##, not "the case of ##5!##".

Yeah, sorry I used 5! first and then realized its remainder was 0 so I added in the 5!+1 to get a 1 remainder.

 

[jedishrfu]

The title is a bit different than your actual question with the example.

That modulo is a ring homomorphism is the principle behind the example. Other theorems and tools in that area are the Chinese remainder theorem, Bézout's identity, Fermat's little theorem, Euler's totient function which is the central subject of RSA encryption (*), the law of quadratic reciprocity, Legendre symbols, Kronecker symbols, Zolotarev's lemma, and Euler's criterion.

(*) Shamir is a nice guy. I had the chance to have lunch with him in the early nineties.

I guess what I'm looking for are things like the distributive law and associative law that describe how the modulo operation works in the context of other arithmetic operations.

Sometimes, I stumble across a problem and find something that works but am not certain if that's a fluke or not. This was such a case. I considered proving it:

PROVE: (a * b) mod 6 = (a mod 6) * (b mod 6)

Define a = 6m+x and b = 6n+y where m,n are integers and x,y are {0,1,2,3,4,5}

(a * b) = (6m+x)*(6n+y) = 36mn + 6my + 6nx + xy

(a * b) mod 6 =  (36mn + 6my + 6nx + xy) mod 6 = xy

(a mod 6) * b mod 6) = (6m+x) mod 6 + (6n+y) mod 6 = (x) (y) = xy

hence (a * b) mod 6 = (a mod 6) * (b mod 6)

I didn't feel comfortable with the proof as I'm using the distributive law of integers in the proof.

 

[jedishrfu]

Thanks for the references they help a lot.

I can see that my proof above is wrong in that I forgot to use mod operator on the distribution:

(a * b) mod 6 = (a mod 6) * (b mod 6) mod 6

and this reference from wikipedia that summarizes the @fresh_42 list:

https://en.wikipedia.org/wiki/Modular_arithmetic

 

[fresh_42]

I guess what I'm looking for are things like the distributive law and associative law that describe how the modulo operation works in the context of other arithmetic operations.

Sometimes, I stumble across a problem and find something that works but am not certain if that's a fluke or not. This was such a case. I considered proving it:

PROVE: (a * b) mod 6 = (a mod 6) * (b mod 6)

Define a = 6m+x and b = 6n+y where m,n are integers and x,y are {0,1,2,3,4,5}

(a * b) = (6m+x)*(6n+y) = 36mn + 6my + 6nx + xy

(a * b) mod 6 =  (36mn + 6my + 6nx + xy) mod 6 = xy

(a mod 6) * b mod 6) = (6m+x) mod 6 + (6n+y) mod 6 = (x) (y) = xy

hence (a * b) mod 6 = (a mod 6) *( b mod 6)

I didn't feel comfortable with the proof as I'm using the distributive law of integers in the proof.

In this case, the fact that modulo is a ring homomorphism answers it.
Say ##a=p\cdot n + s## and ##b=q\cdot n +t## then ##a\equiv s\bmod{n}## and ##b\equiv t\bmod{n}.##
\begin{align*}
a+b&=(p+q)\cdot n + (s+t)\equiv s+ t \bmod{n}\\
a\cdot b&=(pq)\cdot n^2+(pt+qs)\cdot n + s\cdot t\equiv s\cdot t \bmod{n}
\end{align*}
This means that addition, subtraction, and multiplication are respected. Division is an exception since only prime numbers ##n=p## allow a multiplicative inverse of all non-zero numbers ##\{1,2,\ldots,p-1\}.## If ##n## isn't prime, e.g. ##n=6## then there are numbers ##s,t\not\equiv 0 \bmod{n}## such that ##s\cdot t \equiv 0\bmod{n},## e.g. ##2\cdot 3 \equiv 8\cdot (-3) \equiv 0\bmod{6} ## although neither of the numbers ##\{-3,2,3,8\}## themselves are divisible by ##6.## Divisions can only be performed by divisors that are coprime to ##n.## This is automatically true for all non-zero remainders in case ##n=p## is prime.

\begin{matrix}
\pi\, : \,&\mathbb{Z}& \longrightarrow &\mathbb{Z}_n=\{0,1,2,\ldots,n-1\}\\
&a&\longmapsto &\pi(a)=a\bmod{n} =s
\end{matrix}
is a ring homomorphism: ##\pi(a\cdot b)=\pi(a)\cdot \pi(b)\, , \,\pi(a + b)=\pi(a) + \pi(b).##

##\pi## is a projection, i.e. surjective on a single, specific set of remainders as representatives of their equivalence classes, usually the remainders ##\{0,1,\ldots,n-1\},## occasionally ##\{-n/2+1,\ldots,0,\ldots n/2 \}.## ##\pi## is not injective, its kernel is the ideal ##n\mathbb{Z}## since all multiples of ##n## are mapped to ##0.##

 

[PeroK]

I guess what I'm looking for are things like the distributive law and associative law that describe how the modulo operation works in the context of other arithmetic operations.

Sometimes, I stumble across a problem and find something that works but am not certain if that's a fluke or not. This was such a case. I considered proving it:

PROVE: (a * b) mod 6 = (a mod 6) * (b mod 6)

Define a = 6m+x and b = 6n+y where m,n are integers and x,y are {0,1,2,3,4,5}

(a * b) = (6m+x)*(6n+y) = 36mn + 6my + 6nx + xy

(a * b) mod 6 =  (36mn + 6my + 6nx + xy) mod 6 = xy

(a mod 6) * b mod 6) = (6m+x) mod 6 + (6n+y) mod 6 = (x) (y) = xy

hence (a * b) mod 6 = (a mod 6) * (b mod 6)

I didn't feel comfortable with the proof as I'm using the distributive law of integers in the proof.

That's what I tried to show in post #3. In the formal system of modulo 3 arithmetic, the numbers 3, 4, 5 do not exist. There are only the numbers 0, 1, 2. That doesn't answer your question, IMO.

However, modulo arithmetic is also used in the context of solving problems using the remainder on division by 3, say. In this case, all the integers can be used. You might write something like:
$$3n + 1 = 3k^2 + 3k +1 \ mod(3)$$Where ##n, k \in \mathbb Z##.

Your question, as I understand it, is whether the order you reduce things ever makes any difference. The answer is that it makes no difference. You can replace one number by an equivalent number (one that has the same remainder) at any stage.

This is technically partitioning the integers into equivalence classes of equal remainder. And, indeed, you must justify that the remainder is always the same regardless of which members of the equivalence class you choose.

 

[jedishrfu]

Thanks @PeroK, I had skipped your post to address @Mark44 post and then saw @fresh_42 and got distracted with my proof.

 

[WWGD]

In Chinese Remainder Theorem.