Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n$ and $k$ be integers with $1\le k < n$. Form a graph $G$ whose vertices are the integers $0,1,2,...,n-1$. We have an edge joining the vertices $a$ and $b$ provided $$a-b \equiv \pm k \pmod n\;.$$ We were given the example if $n=20$ and $k=6$, then vertex $2$ would be adjacent to vertices $8$ and $16$. I need to find a formula involving $n$ and $k$ for the number of connected components of $G$.

I tried creating other examples, with $k=1$ and $n=2$, with $k=2$ and $n=20$, etc, and the pattern that I seemed to find was that the number of components was equal to $k$. But I know that this cannot be the correct solution since $n$ is not involved in this formula, so I also tried $n \bmod k$ as the formula, which seemed to work. Is $n \bmod k$ a legitimate formula for the number of connected components of $G$?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Start at vertex $0$; it's adjacent to $k\bmod n$. From there you can go to $2k\bmod n$, then to $3k\bmod n$, and so on. There are only finitely many vertices, so at some point you must return to one that you've already visited.

  1. Show that you return to $0$ at step $m$, where $m$ is the smallest positive integer such that $mk$ is a multiple of $n$.

  2. Then show that $m=n/d$, where $d=\gcd(k,n)$. Thus, you've traced out a cycle of length $n/d$, and that cycle is clearly a connected component of $G$.

  3. Show that much the same thing happens no matter where you start: you trace out a cycle of length $n/d$.

If you can do that, you should have little trouble figuring out how many connected components $G$ has.

You may find it helpful to look at the cases $n=10,k=6$ and $n=21,k=15$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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