the most difficult easy question

[logistic_guy]

here is the question

How can we map an integer in \(\displaystyle \bold{Z}\) to an integer in \(\displaystyle \bold{Z}_n\)?

my attemp
i don't what is \(\displaystyle \bold{Z}\) so i do some research and i discovered it's just mean integers

i'm not totally sure but i think the question wants \(\displaystyle \bold{Z} \to \bold{Z}_n\)

i think this is the correct notation because i did a lot of mapping in differential geometry

 

[fresh_42]

We can write for any given integer [imath] z [/imath] and any positive integer [imath] n [/imath][math] z=a\cdot n +r \Longleftrightarrow z\equiv r\pmod{n}[/math] with some unique integer [imath] r [/imath] such that [imath] r\in \mathbb{Z}_n=\{0,1,2,\ldots ,n-1\}. [/imath]
The mapping you are asking for is now [imath]\varphi_n \, : \, z\longmapsto r. [/imath] You can show that [imath] \varphi_n (x+y)=\varphi_n (x)+\varphi_n (y) [/imath] and [imath] \varphi_n (x\cdot y)=\varphi_n (x)\cdot \varphi_n (y). [/imath]

[imath] \varphi_n [/imath] is also called "modulo [imath] n .[/imath]" Everyday occurrences are e.g. a light switch or computer [imath] (n=2) [/imath], or the hour hand on a classical clock [imath] (n=12), [/imath] or the degrees in a circle [imath] (n=360), [/imath] or the days of a week [imath] (n=7). [/imath]

 

[logistic_guy]

We can write for any given integer [imath] z [/imath] and any positive integer [imath] n [/imath][math] z=a\cdot n +r \Longleftrightarrow z\equiv r\pmod{n}[/math] with some unique integer [imath] r [/imath] such that [imath] r\in \mathbb{Z}_n=\{0,1,2,\ldots ,n-1\}. [/imath]
The mapping you are asking for is now [imath]\varphi_n \, : \, z\longmapsto r. [/imath] You can show that [imath] \varphi_n (x+y)=\varphi_n (x)+\varphi_n (y) [/imath] and [imath] \varphi_n (x\cdot y)=\varphi_n (x)\cdot \varphi_n (y). [/imath]

[imath] \varphi_n [/imath] is also called "modulo [imath] n .[/imath]" Everyday occurrences are e.g. a light switch or computer [imath] (n=2) [/imath], or the hour hand on a classical clock [imath] (n=12), [/imath] or the degrees in a circle [imath] (n=360), [/imath] or the days of a week [imath] (n=7). [/imath]

thank

you say \(\displaystyle r \in \bold{Z}_n\)

if \(\displaystyle r = 12\) and \(\displaystyle n = 10\)

\(\displaystyle \bold{Z}_n = \{0,1,2,3,4,5,6,7,8,9\}\) i don't see \(\displaystyle 12\) there

 

[fresh_42]

thank

you say \(\displaystyle r \in \bold{Z}_n\)

if \(\displaystyle r = 12\) and \(\displaystyle n = 10\)

\(\displaystyle \bold{Z}_n = \{0,1,2,3,4,5,6,7,8,9\}\) i don't see \(\displaystyle 12\) there

[imath] z [/imath] and [imath] n [/imath] are input, [imath] r [/imath] is the output: division of [imath] z [/imath] by [imath] n [/imath] with remainder [imath] r. [/imath] Such a division can be performed such that the remainder is between [imath] 0 [/imath] and [imath] n. [/imath] This set of remainders is thus [imath] \{0,1,\ldots,n-1\} [/imath] and usually denoted by [imath] \mathbb{Z}_n. [/imath] The whole theoretical situation is a bit more complicated but I don't want to create confusion. It has to do with the fact, that we could as well use for example [imath] 1,2,\ldots,n [/imath] as possible remainders, but starting with zero instead of ending with [imath] n [/imath] makes things easier.

Anyway, we do not choose [imath] r, [/imath] we compute it. For [imath] z=12 [/imath] and [imath] n=10, [/imath] we get [imath] 12=1\cdot 10 +2 [/imath] so [imath] r=2 \in \{0,1,2,3,4,5,6,7,8,9\}=\mathbb{Z}_{10}. [/imath]

 

[logistic_guy]

[imath] z [/imath] and [imath] n [/imath] are input, [imath] r [/imath] is the output: division of [imath] z [/imath] by [imath] n [/imath] with remainder [imath] r. [/imath] Such a division can be performed such that the remainder is between [imath] 0 [/imath] and [imath] n. [/imath] This set of remainders is thus [imath] \{0,1,\ldots,n-1\} [/imath] and usually denoted by [imath] \mathbb{Z}_n. [/imath] The whole theoretical situation is a bit more complicated but I don't want to create confusion. It has to do with the fact, that we could as well use for example [imath] 1,2,\ldots,n [/imath] as possible remainders, but starting with zero instead of ending with [imath] n [/imath] makes things easier.

Anyway, we do not choose [imath] r, [/imath] we compute it. For [imath] z=12 [/imath] and [imath] n=10, [/imath] we get [imath] 12=1\cdot 10 +2 [/imath] so [imath] r=2 \in \{0,1,2,3,4,5,6,7,8,9\}=\mathbb{Z}_{10}. [/imath]

i think i'm understanding. why not write it like \(\displaystyle r \equiv z \ \text{mod} \ n\) instead of \(\displaystyle z \equiv r \ \text{mod} \ n\)?

 

[fresh_42]

i think i'm understanding. why not write it like \(\displaystyle r \equiv z \ \text{mod} \ n\) instead of \(\displaystyle z \equiv r \ \text{mod} \ n\)?

[imath] \equiv [/imath] is an equivalence relation, which means it is reflexive [imath] z\equiv z, [/imath] symmetric [imath] x\equiv y \Longrightarrow y\equiv x, [/imath] and transitive [imath] a\equiv b \text{ and } b\equiv c \Longrightarrow a\equiv c .[/imath]

So symmetry says that it makes no difference what you write first.

 

[logistic_guy]

[imath] \equiv [/imath] is an equivalence relation, which means it is reflexive [imath] z\equiv z, [/imath] symmetric [imath] x\equiv y \Longrightarrow y\equiv x, [/imath] and transitive [imath] a\equiv b \text{ and } b\equiv c \Longrightarrow a\equiv c .[/imath]

So symmetry says that it makes no difference what you write first.

\(\displaystyle r \ \text{mod} \ n \) mean the remainder of \(\displaystyle \frac{r}{n}\), isn't it?

\(\displaystyle z \equiv r \ \text{mod} \ n \), it's like \(\displaystyle z\) is the remainder

if \(\displaystyle g \equiv h \ \text{mod} \ n \) is the same as \(\displaystyle h \equiv g \ \text{mod} \ n \), we won't know which one is the remainder

 

[fresh_42]

Note: The notation [imath] a\equiv b\pmod{n} [/imath] does not require that either of them is within the set of minimal remainders [imath] \{0,1,\ldots ,n-1\}. [/imath] [imath] 50 \equiv 22\pmod{7} [/imath] is perfectly fine. The minimality only kicks in if we want to end up in [imath] \mathbb{Z}_n [/imath] and want to represent the elements of [imath] \mathbb{Z}_n [/imath] by the numbers [imath] \{0,1,\ldots ,n-1\}. [/imath] The notation [imath] a\equiv b\pmod{n} [/imath] only says that [imath] a [/imath] and [imath] b [/imath] have the same remainder by division by [imath] n, [/imath] not which one: [imath] 50=7\cdot 7+1= 4\cdot 7 +22 .[/imath] This is where a rigorous treatment becomes a bit more complicated.

 

[fresh_42]

We actually sort the set of integers into equivalent classes, namely
[math]\begin{array}{lll} \mathbb{Z}&=(\{0\}+n\cdot\mathbb{Z}) \cup (\{1\}+n\cdot\mathbb{Z}) \cup (\{2\}+n\cdot\mathbb{Z}) \cup \ldots (\{n-1\}+n\cdot\mathbb{Z})\\[6pt] &=\{\ldots,-2n,-n,0,n,2n,\ldots\}\cup \{\ldots,1-2n,1-n,1,1+n,1+2n,\ldots\}\cup \ldots \cup \{\ldots,-1-2n,-1-n,-1,n-1,2n-1,\ldots\} \end{array}[/math]The first set contains all multiples of [imath] n [/imath] that correspond to the minimal remainder [imath] 0. [/imath]
The second set contains all multiples of [imath] n [/imath] plus [imath] 1 [/imath] that correspond to the minimal remainder [imath] 1. [/imath]
etc.
The last set contains all multiples of [imath] n [/imath] plus [imath] n-1 [/imath] that correspond to the minimal remainder [imath] n-1. [/imath]

Since every set belongs to a certain minimal remainder, we say that these minimal remainders from [imath] 0 [/imath] to [imath] n-1 [/imath] represent their equivalence class. We calculate with the minimal remainders in [imath] \{0,1,2,\ldots,n-1\} [/imath] instead of with entire sets. However, the notion [imath] a\equiv b\pmod{n} [/imath] (and of course [imath] a \not\equiv b\pmod{n} [/imath]) is allowed for all integers, not only for the minimal remainders. Of course, people would write [imath] 50\equiv 1\pmod{7} [/imath] instead of [imath] 50\equiv 22\pmod{7} [/imath], but allowed are both since [imath] 50,22,1 [/imath] all belong into the same set of remainders, the second one in the above list: [imath] \{\ldots , 1-14,1-7,1,1+7,1+14,1+21,\ldots\}=\{\ldots, -20,-13,-6,1,8,15,22,29,36,43,50,57,\ldots\}. [/imath]

 

[logistic_guy]

with this notation \(\displaystyle 50 \equiv 1 \ \text{mod} \ 7\) it's clear \(\displaystyle 1\) is the remainder

with this notation \(\displaystyle 50 \equiv 22 \ \text{mod} \ 7\) many will think \(\displaystyle 22\) is the remainder i say bad notation

with this notation \(\displaystyle g \equiv h \ \text{mod} \ n\) people who use the first notation will think \(\displaystyle h\) is the remainder and people like me will think \(\displaystyle g\) is the remainder

is there a notation that emphasize on the remainder something like \(\displaystyle 1 = 50 \ \text{mod} \ 7\) give no doubt \(\displaystyle 1\) is the remainder

 

[fresh_42]

with this notation \(\displaystyle 50 \equiv 1 \ \text{mod} \ 7\) it's clear \(\displaystyle 1\) is the remainder

with this notation \(\displaystyle 50 \equiv 22 \ \text{mod} \ 7\) many will think \(\displaystyle 22\) is the remainder i say bad notation

with this notation \(\displaystyle g \equiv h \ \text{mod} \ n\) people who use the first notation will think \(\displaystyle h\) is the remainder and people like me will think \(\displaystyle g\) is the remainder

is there a notation that emphasize on the remainder something like \(\displaystyle 1 = 50 \ \text{mod} \ 7\) give no doubt \(\displaystyle 1\) is the remainder

Only the line [imath] 50=7\cdot 7 +1, [/imath] noted as Euclidean division. If it is written that way, then it is assumed that [imath] 0\leq r=1 \leq 6. [/imath] E.g., we can also divide polynomials like [imath] (x^3 +3x^2+4x+5):(x^2+2x+2)=x+1 [/imath] with remainder [imath] 3. [/imath] We can write it as [imath] (x^3 +3x^2+4x+5)=(x+1)\cdot (x^2+2x+2) +3 [/imath] in which case we have [imath] 0\leq \deg(r)=\deg 3 \leq (\deg(x^2+2x+2))-1. [/imath] The degree now measures the magnitude of the remainder that is less then two. Euclidean division requires a minimal remainder. For the [imath] \equiv [/imath] relation on the other hand, equivalence is important. We want to write the integers as the union of these sets I mentioned. We actually calculate with those sets. It's only easier to abbreviate them by one of their elements, and for the sake of clarity, those in [imath] \{0,1,\ldots,n-1\}. [/imath] But what we really mean are the sets. I told you it's a bit more complicated.

And, [imath] 22 [/imath] is also a remainder, namely [imath] 50=4\cdot 7 +22, [/imath] just not the smallest. Now, [imath] 22=3\cdot 7+1, [/imath] i.e. [imath] 22\equiv 1\pmod{7}. [/imath] By transitivity, we get [math] 50\equiv 22\pmod{7} \text{ and }22\equiv 1\pmod{7}\Longrightarrow 50\equiv 1\pmod{7}. [/math]
If you only want to divide, then you can use Euclidean division. The notation [imath] \equiv [/imath] is for number theory.

 

[logistic_guy]

i still don't understand the big deal of using \(\displaystyle 22\)

\(\displaystyle \frac{50}{7} = 1\frac{43}{7} = 2\frac{36}{7} = 3\frac{29}{7} = 4\frac{22}{7} = 5\frac{15}{7} = 6\frac{8}{7} = 7\frac{1}{7}\)

anyone who get the fraction \(\displaystyle \frac{50}{7}\) will say the answer \(\displaystyle 7\frac{1}{7}\) without all this complication

why i need to say \(\displaystyle 50\) and \(\displaystyle 43\) and \(\displaystyle 36\) and \(\displaystyle 29\) and \(\displaystyle 22\) and \(\displaystyle 15\) and \(\displaystyle 8\) have a remainder of \(\displaystyle 1\)

why i need transivity to jump from number to number when i can directly say the remainder is \(\displaystyle 1\)

 

[fresh_42]

[imath] 22 [/imath] was only an example.

The point is, that we calculate with these sets
[math]\begin{array}{lll} [0]&=0+7\cdot\mathbb{Z}= \{\ldots,-21,-14,-7,0,7,14,21,\ldots\}\\[6pt] [1]&=1+7\cdot\mathbb{Z}= \{\ldots,-20,-13,-6,1,8,15,22,\ldots\}\\[6pt] [2]&=2+7\cdot\mathbb{Z}= \{\ldots,-19,-12,-5,2,9,16,23,\ldots\}\\[6pt] [3]&=3+7\cdot\mathbb{Z}= \{\ldots,-18,-11,-4,3,10,17,24,\ldots\}\\[6pt] [4]&=4+7\cdot\mathbb{Z}= \{\ldots,-17,-10,-3,4,11,18,25,\ldots\}\\[6pt] [5]&=5+7\cdot\mathbb{Z}= \{\ldots,-16,-9,-2,5,12,19,26,\ldots\}\\[6pt] [6]&=6+7\cdot\mathbb{Z}= \{\ldots,-15,-8,-1,6,13,20,27,\ldots\} \end{array}[/math]and any member of each set as representative is as appropriate as any other. The representatives [imath] [0],\ldots,[6] [/imath] are only the most convenient ones for most purposes. These sets are the elements of [imath] \mathbb{Z}/7\cdot \mathbb{Z}. [/imath] We can add and multiply them. These arithmetic operations are the same as if we applied them on the remainders [imath] 0,1,2,3,4,5,6 [/imath] modulo [imath] 7. [/imath]

These (minimal, non-negative) remainders build the so-called ring [imath] \mathbb{Z}_n [/imath] and "behave the same as" is mathematically written as [math] \mathbb{Z}/n\cdot \mathbb{Z} \cong \mathbb{Z}_n. [/math]The LHS are the sets, and the RHS the numbers [imath] \{0,1,2,3,4,5,6\}. [/imath] Your initial map was [math] \mathbb{Z}\twoheadrightarrow \mathbb{Z}/n\cdot \mathbb{Z} \cong \mathbb{Z}_n. [/math]And before you dig even deeper, I better phrase it correctly: [imath] \mathbb{Z} \rightarrow \mathbb{Z}_n [/imath] is the surjective part of the short exact sequence
[math] \{0\} \rightarrowtail n\cdot \mathbb{Z} \rightarrowtail \mathbb{Z} \twoheadrightarrow \mathbb{Z}/n\cdot \mathbb{Z} \cong \mathbb{Z}_n \twoheadrightarrow \{0\}[/math]of ring homomorphisms.

I told you that the details are a bit more complex. The essential point is that we divided the integers into seven sets and that we can do arithmetic with these sets. However, sets are inconvenient to handle and large to write down. We therefore abbreviate them by [imath] [0],[1],[2],[3],[4],[5],[6] [/imath] and because mathematicians are lazy, we only write [imath] 0,1,2,3,4,5,6. [/imath] These numbers are cyclic: [imath] 6+1=0. [/imath] To distinguish that from ordinary additions and multiplications we write [imath] 6+1=0 \pmod{7} [/imath] and I personally even go a step further and write [imath] 6+1\equiv 0\pmod{7} [/imath] to remind per notation that we actually meant those sets.

But before you lose interest: one can do fancy encryption things with those remainders.

 

[logistic_guy]

thank fresh_42

again you explaint it nicely. i won't say i understand everything but i'll make this post reference. i'll come back here whenever i face similar questions