2
$\begingroup$

Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and 3, and an edge between 5 and 2. What is the length of the shortest path between 0 and 1?

My method to get the answer is to apply the definition of congruence. The edge exits iff $7 | x + 3 - y$. Thus, I got one cyclic graph and then get the answer is 2. Is there any method I can play with modular arithmetic without drawing a graph so that I can get shortest path between node 0 and node 1?

$\endgroup$
2
$\begingroup$

Let us consider the more general case in which you have $n$ vertices, and you connect $x,y$ if $x-y \equiv a \pmod{n}$ (in your case, $n = 7$ and $a = 3$).

Your graph is a union of disjoint cycles. When $n$ is prime (as in your case), it is a single cycle. Hence if you want to get from $x$ to $y$, either you keep adding $a$ (modulo $n$), of you keep subtracting $a$ (modulo $n$). If you add $m$ times the value $a$ (where $m$ is possibly negative) then $x+ma \equiv y \pmod{n}$, that is, $ma \equiv y-x \pmod{n}$. Let us now assume that $(a,n) = 1$ (for example, $n$ is prime and $1 \leq a \leq n-1$). Then $m \equiv a^{-1}(y-x) \pmod{n}$.

Solving the equation above (assuming $x \not\equiv y \pmod{n}$), there will be one solution $m_+$ in the range $1,\ldots,n-1$ and another $m_-$ in the range $-1,\ldots,-(n-1)$. The distance is $\min(m_+,-m_-)$.

In your case, $n = 7$ and $a = 3$. We can compute $a^{-1} = 5$. If $x = 0$ and $y = 1$ then $a^{-1}(y-x) = 5$, and so $m_+ = 5$ and $-m_- = 2$. So the shortest path goes backwards for two steps: $0 \to 4 \to 1$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You need to find integers $a$ and $b$ such that

$3a = 7b + 1$

and from all the (infinitely many) values of $a$ you want the one that minimises $|a|$. In this case, we can see by trial and error that the set of solutions is $a=5+7n$ for integer values of $n$, and to minimise $|a|$ we take $n=-1$, so that $a=-2$, and the shortest path is $0 \to 4 \to 1$.

In general, there will be infinitely many solutions to $pa = qb + 1$ as long as $p$ and $q$ are co-prime (do not share any common factors other than $1$), and you can use the Euclidean algorithm to find the smallest positive value of $a$. If the smallest positive value of $a$ is $a_0$ then the value of $a$ that minimises $|a|$ is either $a_0$ or $a_0 - q$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

We can easily generalize this problem: Given a finite group G, two elements g and h in G, and a subset S of G, find the shortest path from g to h in the graph whose vertices are the elements of G and whose edges are the elements of S or the respective inverses of the elements of S, i.e., two vertices x and y are adjacent if and only if y=xr for some r that is either an element of S or is an inverse of some element of S. Note that this graph has |G| vertices and |S||G| edges in an explicit or implicit computer implementation. A simple breadth-first search algorithm on this graph starting at the vertex g and terminating once the vertex h is reached will yield the shortest path between g and h in time O(|G| + |S||G|)=O(|S||G|) time. Moreover, we do not actually have to construct this graph; this is because we already know what all the edges are. We just have to loop through the neighbors of the current group element at every iteration of the breadth-first search algorithm.

In your case, for any positive integer n, we have S={3 mod n} and that the order of the additive group of residue classes mod n is n, so we can find the shortest path between any two specified residue classes mod n in O(n)=O(n) time.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.