# Shortest path in modular arithmetic

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?

## 3 Answers

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

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

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.