Wikipedia:Reference desk/Archives/Mathematics/2017 September 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 26

Term for toroidal directed graph

Is there an established term in graph theory for those directed graphs which, for some nonnegative integer n and positive integer b, can be constructed as follows?

1. Start with a single vertex.
2. Replace the entire graph with b copies of it, numbered from 0 to b - 1.
3. For each vertex in the original and each integer 0 ≤ i < b, add an edge from the version in copy i to the version in copy i + 1 mod b.
4. Repeat steps 2 and 3 until they've taken place n times.

For b = 2, such a graph is the hypercube graph Q_n with each undirected edge changed to a reciprocal pair of directed edges. For n = 1 it's a directed cycle of length b. For b = 1 or n = 0 it's a single vertex. Its symmetric closure is the topology of a torus interconnect. NeonMerlin 04:11, 26 September 2017 (UTC)

Sounds like you're taking powers of a cycle, using the Cartesian product of graphs. --JBL (talk) 13:45, 27 September 2017 (UTC)

Modular arithmetic properties

Given ${\begin{matrix}a_{1}\equiv b_{1}{\pmod {n}}\\a_{2}\equiv b_{2}{\pmod {n}}\end{matrix}}$ , please prove for me the properties

${\begin{aligned}\forall k\in \mathbb {Z} :&{\begin{cases}a+k\equiv b+k{\pmod {n}}\\ak\equiv bk{\pmod {n}}\\a^{k}\equiv b^{k}{\pmod {n}}\end{cases}}\\a_{1}\pm a_{2}&\equiv b_{1}\pm b_{2}{\pmod {n}}\\a_{1}a_{2}&\equiv b_{1}b_{2}{\pmod {n}}\\{\Big (}ak&\equiv bk{\pmod {n}}\ \Rightarrow \ a\equiv b{\pmod {n}}{\Big )}\iff k\perp n\\\end{aligned}}$

יהודה שמחה ולדמן (talk) 17:23, 26 September 2017 (UTC)

• Is that homework? All of them except the last one are fairly easy. Start by writing what it means that $a\equiv b{\pmod {n}}$, and see what follows about a+k, ak, etc.

As for the last one, while I intuitively see what it means (and it is true), you should try to be very careful with the quantifiers you use and in which order. Tigraan^{Click here to contact me} 17:52, 26 September 2017 (UTC)

No homework – I just can't see it. Even through the definition ${\begin{matrix}a=pn+r\\b=qn+r\end{matrix}}$ I still can't understand the "first" property. Where is my head? יהודה שמחה ולדמן (talk) 18:06, 26 September 2017 (UTC)

Your first equation after the givens introduces two new variables a and b which weren't mentioned before. I'm guessing these are intended to be a₁ and b₁ (which would of course equally apply to a₂ and b₂). Ok, so by the definition of congruence, you are given

$\exists r:{\begin{matrix}a_{1}-b_{1}=rn\end{matrix}}$

so ${\begin{matrix}(a_{1}+k)-(b_{1}+k)=rn\end{matrix}}$

and by definition that means ${\begin{matrix}a_{1}+k\equiv b_{1}+k{\pmod {n}}\end{matrix}}$

For most of these you can similarly use the congruence definition to convert to a normal equation, do a simple algebraic manipulation, then convert back to a congruence relation. CodeTalker (talk) 21:50, 26 September 2017 (UTC)

We have

$a\equiv b{\pmod {n}}.$

is just a another way of writing

$a=kn+b,$

So proving the properties is really easy

a + g ≡ b + g (mod n)

becomes

$a+g=kn+b+g,$

$(a+g)=kn+(b+g),$

$newa=kn+newb,$

$newa\equiv newb{\pmod {n}}.$

Here is another one

g a ≡ g b (mod n)

becomes

$g*a=g*(kn+b),$

$g*a=g*kn+g*b,$

$newa=g*kn+newb,$

$newa=newk*n+newb,$

$newa\equiv newb{\pmod {n}}.$

110.22.20.252 (talk) 07:25, 27 September 2017 (UTC)

I think I should ask a silly question here (this just shows how slow am I):

Which one of these is true? ${\begin{matrix}a\equiv b{\pmod {n}}\ \implies \ a-b=kn\\a\equiv b{\pmod {n}}\ \iff \ a-b=kn\end{matrix}}$ . יהודה שמחה ולדמן (talk) 09:46, 27 September 2017 (UTC)

They are both true, but the second is stronger and includes everything the first says. Double sharp (talk) 09:52, 27 September 2017 (UTC)

That is the definition of a = b (mod n) and totally equivalent to it. The . = . (mod .) is not the normal arithmetical equality, it is modulo n equality, b (mod n) does not mean much on its own. Dmcq (talk) 10:46, 27 September 2017 (UTC)

True. I understant what Congruence means. Then how do we prove $a-b=kn\implies \ a\equiv b{\pmod {n}}$ ?

All I know right now is $a-b=kn\implies \ a-b\equiv 0{\pmod {n}}$ . Now what? יהודה שמחה ולדמן (talk) 14:09, 27 September 2017 (UTC)

Umm. Add b to both sides of the equation? Double sharp (talk) 14:53, 27 September 2017 (UTC)

Even simpler - it is true by definition. $a-b\equiv 0{\pmod {n}}$ or $a\equiv b{\pmod {n}}$ are just more compact ways of writing $a-b=kn$ for some integer k. See modular arithmetic. Gandalf61 (talk) 15:05, 27 September 2017 (UTC)

I don't think so. I think you are mistaking with $a\equiv b{\pmod {n}}\ \Rightarrow \ {\begin{cases}a=pn+r\\b=qn+r\end{cases}}\ \Rightarrow \ a-b=kn\ \Rightarrow \ a-b\equiv 0{\pmod {n}}$ .

We need to show $\Leftarrow$ . יהודה שמחה ולדמן (talk) 15:31, 27 September 2017 (UTC)

You just wrote a chain of implications. Which one of those gives you trouble to get the reciprocal? Tigraan^{Click here to contact me} 15:42, 27 September 2017 (UTC)

$a-b\equiv 0{\pmod {n}}\ \Rightarrow \ a-b=kn\ \Rightarrow \ a=kn+b$

By the Euclidean algorithm

$\exists q,r\in \mathbb {Z} :0\leq r<n:b=qn+r$

Hence,

${\begin{aligned}&\Rightarrow \ a=kn+(qn+r)\ \Rightarrow \ {\begin{cases}a=(k+q)n+r\\b=qn+r\end{cases}}\ \Rightarrow \ a\equiv b{\pmod {n}}\\&\blacksquare \end{aligned}}$ . יהודה שמחה ולדמן (talk) 16:14, 27 September 2017 (UTC)

Why on earth are you writing all that stuff? a=b (mod n) is equivalent to a=b+kn which is the same as a-b=kn which is equivalent to (a-b) = 0+kn and therefore to a-b=0 (mod n). Dmcq (talk) 16:35, 27 September 2017 (UTC)

Wait, is it an "equivalence" or an "implication"? Are these to words the same thing?

You proved $\Rightarrow$ , I proved $\Leftarrow$ . Hence $\iff$ . It is called Rigour. יהודה שמחה ולדמן (talk) 17:14, 27 September 2017 (UTC)

I was meaning that they are all equivalent to each other. The two at the ends simply rewrite expressions using the definition of a = b (mod n). In between a bit of simple algebra is used where we subtract a value from both sides of an equation, that does not do anything strange and can be reversed easily by adding the same value to both sides. Dmcq (talk) 17:24, 27 September 2017 (UTC)

At this point, I think it's fair to say that it's not rigor, but rigor mortis. --Deacon Vorbis (talk) 17:40, 27 September 2017 (UTC)