Shortest path in modular arithmetic

Question

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?

Answer 1

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$.

Answer 2

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$.

Answer 3

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.