An odd (potential) primality test My friend and I were talking about primality testing, and he showed me a really neat way to test if something is prime or not. The thing is, we have no idea how it works.
So, we want to test if $n$ is prime. Draw an $n$-gon. Start at any vertex, and draw a line from that point to the adjacent vertex (this can be any direction as long as it's consistent through the whole process). Then go from that vertex, and go over two vertices. Start there and go over 3 vertices, etc. until the pattern repeats itself. 
For example, if $n$ is $5$ we draw a pentagon:
       • (a)

 • (e)       • (b)


  • (d)     • (c)

And A->B, then B->D, then, D->B, then B->A, and finally A->A (you don't have to draw anything). The sequence then repeats itself infinitely so we stop there. What we've found is that for any $n$-gon where $n$ is prime (and only when $n$ is prime), no vertices have more than one line drawn to them. Intuitively I have some idea of why this means it's prime, but I can't exactly grasp it. 
Pictures:


Why does this work? Does it even work past a certain number? What's the mathematical principle behind it, and can we represent this test mathematically without drawing shapes?
 A: Note: this is not a complete solution, but rather, a not-too-beautifully constructed proof of half the claim ("If you get multiple hits, then $n$ isn't prime"), with a brief discussion of why the other half might be true, but why it's a bit marginal, and leaves me doubting that it works. 
The vertices you hit (assuming the starting vertex is labelled $0$ are of the form
$$
1\\
1 + 2\\
1 + 2 + 3 \\
\ldots
$$
all $\bmod n$, where $n$ is the number you're testing for primality. 
These can be rewritten in the form $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, so you're getting vertices
$$
1\\
\frac{1(2)}{2} \\
\frac{2(3)}{2} \\
\frac{3(4)}{2} \\
\frac{4(5)}{2} \\
\ldots
$$
(again, all $\bmod n$). Suppose that two of these are equal, i.e., that 
$$
\frac{u(u+1)}{2}  = \frac{v(v+1)}{2} \bmod n 
$$
Then 
$$
u^2 + u - v^2 - v = 0 \bmod n
$$
and thus
$$
(u+v)(u-v) + (u-v) = 0 \bmod n
$$
and hence
$$
(u+v+1)(u-v) = 0 \bmod n
$$
Now since $u$ and $v$ are distinct, that means that $u-v$ divides $n$, and (if it's not $1$) that $n$ is not prime. 
So I guess that shows that if you get a repeat, then $n$ is not prime. 
What's not clear is that if $n$ is not prime, then you must get repeats, for if your polygon comes back to vertex $0$ after some numbers of steps less than, say, $\sqrt{n}$, then there might be a factor that you "never get a chance to see." On the other hand, in $\sqrt{n}$ steps, you only get a sum that's $\sqrt{n} (\sqrt{n} + 1)$ in size, i.e., $n + \sqrt{n}$. So this is right on the margin. 
It's POSSIBLE that the loop closes up in just under $\sqrt{n}$ steps, but that $n$ itself happens to be the square of a prime. You'd have to prove that can't happen before I'd believe the "only if" part of the claim. 
(And hence, as @Bram28 / @Nilknarf observe, you don't have a primality checker until you do this "marginal" part.) 
A: If we number the vertices from $0$ to $p-1$ and start at vertex $0$
Then we can describe the circuit as $S_n = \sum_\limits {i=1}^n i \pmod p$
If $p$ is prime, then each vertex is attached to no more than $2$ lines.
However, this is not an "if and only if" proposition.  i.e. it fails when $p=4$ and not a "prime checker"
Proving it the one way...
If $p = 2$ the graph is trivial.
if $p$ is odd, when we reach $k=\frac {p-1}{2}$
$S_{k+1} = S_{k-1}$
i.e.  $S_k + \frac {p+1}{2} \equiv S_k + \frac {p+1}{2} - p \equiv S_k - \frac {p-1}{2} \pmod p$
and it is easy enough to show that $S_n = S_{p-n-1}$ and the circuit doubles back on itself.
We need to show for all  $m,n: 0\le n,m \le \frac {p-1}{2}, S_n-S_m \ne 0$ and $m\ne n$ 
$S_n-S_m \equiv 0\pmod p$
$S_n-S_m = \frac 12 (n-m)(n+m+1)$
And with $p$ prime, there is impossible for two numbers smaller than $p$ to have a product that is a multiple of $p$
A: 
I would like to add this explanation as a complement to the rest of answers. I think that the problem can be stated as a rotation problem of $D_n$, the Dihedral group of the $n$-gon. This is only the statement and an explanation of the equivalence.

When you trace a line from vertex $v_i$ to vertex $v_j$, imagine that you are not joining them with a line, but rotating to the right the $n$-gon, $k$ times $\frac{360}{n}$ degrees (the angle between two consecutive vertices) where $k$ is the total of rotations of one vertex $v_i$ to the closest vertex $v_{i+1}$, in the decided rotating direction to the desired final $v_j$ that you need to arrive at $v_j$ from $v_i$. 
The Caley table of the Dihedral group of the $n$-gon, $D_n$, shows the composition operation between the elements of $D_n$. The composition operation of rotations basically is defined as $$r_ir_j=r_{i+j \pmod {n}}$$
... where $i,j \in [0..n-1]$. The operation is right to left: we apply rotation $r_i$ to the already made rotation $r_j$. The composition operation is the group operation of $D_n$.
Supposing that $I=r_0$ is the initial position of the $n$-gon at the beginning of the conjecture, then you rotate $r_1$ times the angle between two consecutive vertices (this is rotating $\frac{360}{n} \cdot 1$ degrees to the right), then you rotate $r_2$ times ($\frac{360}{n} \cdot 2$ degrees to the right), then three times, etc.
The "jumps", or lines traced between vertices, are equivalent to rotations. Jumping $20$ vertices will be equivalent to applying the $n$-Dihedral group rotation $r_{20 \pmod {n}}$.
So basically $r_{i+1 \pmod {n}}r_{i \pmod {n}} = r_{i+1+i \pmod {n}} =r_{2i+1 \pmod {n}}$. So it is equivalent to make operations in the rotations of the Caley table of $D_n$.
This is an example of $D_5$
$$\begin{array}{|c|c|c|c|c|c|}
\hline
& r_0& r_1 & r_2 & r_3 & r_4 \\ \hline
r_0 & \color{red}{r_0} & \color{red}{r_1} & r_2 & r_3 & r_4 \\ \hline
r_1 & r_1 & r_2 & \color{red}{r_3} & r_4 & \color{red}{r_0} \\ \hline
r_2 & r_2 & r_3 & r_4 & r_0 & r_1 \\ \hline
r_3 & r_3 & r_4 & r_0 & \color{red}{r_1} & r_2 \\ \hline
r_4 & r_4 & r_0 & r_1 & r_2 & r_3 \\ \hline
\end{array}$$
As per your conjecture, we start at $r_0$ (column). We will mark in red $r_0$ because we will assume that the first movement of the conjecture is rotate $0$ degrees, so $r_0r_0=r_0$. Then we apply to the current rotation type, that happens to be again $r_0$, a rotation $r_1$, so we are at $r_1$, now again going to the column $r_1$ now we will apply a rotation of $r_2$, so $r_2r_1=r_3$, so we will mark $r_3$ in red... if we continue the algorithm, we will arrive to a Caley table in which every column has only one visited rotation type. 
If we find two rows with the same rotation type marked in red, means that a vertex has more than two lines entering or exiting it.
But, as the other answer said, also holds for $D_{2^t}$ cases, for instance $D_4$
$$\begin{array}{|c|c|c|c|c|}
\hline
& r_0& r_1 & r_2 & r_3 \\ \hline
r_0 & \color{red}{r_0} & \color{red}{r_1} & r_2 & r_3 \\ \hline
r_1 & r_1 & r_2 & \color{red}{r_3} & r_0  \\ \hline
r_2 & r_2 & r_3 & r_0 & r_1 \\ \hline
r_3 & r_3 & r_0 & r_1 & \color{red}{r_2} \\ \hline
\end{array}$$
And apart from those cases, we will find two red marks $\color{red}{r_3}$ with the same rotation type, for $D_{6}$:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline
& r_0& r_1 & r_2 & r_3 & r_4 & r_5 \\ \hline
r_0 & \color{red}{r_0} & \color{red}{r_1} & r_2 & r_3 & \color{red}{r_4} & r_5 \\ \hline
r_1 & r_1 & r_2 & \color{red}{r_3} & r_4 & r_5 & r_0 \\ \hline
r_2 & r_2 & r_3 & r_4 & r_5 & r_0  & r_1 \\ \hline
r_3 & r_3 & r_4 & r_5 & \color{red}{r_0} & r_1 & r_2 \\ \hline
r_4 & r_4 & r_5 & r_0 & r_1 & r_2 & \color{red}{r_3} \\ \hline
r_5 & r_5 & r_0 & r_1 & r_2 & r_3 & r_4 \\ \hline
\end{array}$$
If we use the Caley table to perform the same original algorithm that the OP defined, then our stop condition is arriving to a rotation of $n-1$ vertices successfully or marking for the second time in red the same rotation type (as in the former case happened with $r_3$).
So basically if my expressions above are correct, your conjecture (including the observation that also the set $2^t$ holds) can be stated as:

$\forall D_n\ ${$\not \exists r_a,r_b,r_c,r_d,r_e \in D_n, a \not = b \ ,\ r_c r_a=r_e \land r_dr_b=r_e $}$ \to n \in \Bbb P\ \cup\ ${$2^t,t \in \Bbb N, t \ge 2$}
  where $D_n$ is the Dihedral group of the $n$-gon.

or equivalently:

Def. Set $E_n = ${$e_k: e_k=r_k r_{k-1}...r_0, k \in \Bbb N, k \lt n $}
$\forall D_n\ ${$\not \exists e_i,e_j,i \not = j \in E_n: e_i=e_j $}$ \to n \in \Bbb P\ \cup\ ${$2^t,t \in \Bbb N, t \ge 2$}

That would be the initial point for a demonstration. I am currently reading the book "Symmetry: A Mathematical Exploration (Springer, Kristopher Tapp)" and this conjecture fits very well with the basic concepts explained about the Dihedral group in the book. Is a good reading for beginners (like myself).
