Let p be an odd prime. (Generalizations to p simply being an odd number way at end of this article.) Suppose a tie is folded with proportion a / p to the left of the fold and proportion b / p to the right of the fold, with a + b = p. Precisely one of a or b is even.
Define a tie-folding to be the maneuver that folds the portion of tie with even numerator in half to change the fraction pair (a/p, b/p) with a + b = p into a new fraction pair of the same form. The example below shows a starting pair (3/11, 8/11) and illustrates what happens after a fold.
Result 1: Starting with a given fraction pair (a/p, b/p), one is sure to return to this same fraction pair after a finite number of tie-folds.
Proof: As there are only finitely many fraction pairs to consider, repeated folding must fall into a cycle. Could (a/p, b/p) fail to be part of that cycle?
If so, as the diagram suggests, there would be a fraction pair (c/p, d/p) with two “parent pairs.”
But the parent of (c/p, d/p) can only be of the form (2c/p, *) or of the form (*, 2d/p) if these are valid fraction pairs. Since c + d = p, only one of the numbers c or d is less than half p (they cannot each equal p/2 as this is not an integer, and they both can’t be less than p/2 as
c + d = p). Thus only one of 2c or 2d is less than p giving a valid faction pair.
Different primes p exhibit different cycle behaviors.
Example: p=11
All fraction pairs are in terms of elevenths. We have
(1, 10) -> (6, 5) -> (3, 8) -> (7, 4) -> (9, 2) -> (10, 1) -> (5, 6) -> (8, 3) -> (4, 7) -> (2, 9) -> repeat
There is one cycle of length 10, which is p − 1, and all possible fractions appear on the left side of the fold (and each also appears five moves forward on the right side of the fold). This cycle is its own mirror image (meaning that if (a, b) appears in the cycle, then (b, a) also appears in the cycle, that is, fractions that appear on the left of the fold later appear on the right, and vice versa). In fact, the second half of the cycle is the mirror image of the first half.
Example: p = 7
All fraction pairs are in terms of sevenths. We have
(1, 6) -> (4, 3) -> (2, 5) -> repeat
(6, 1) -> (3, 4) -> (5, 2) -> repeat
The fraction pairs break into two cycles each of length 3, which is half of p −1, with one cycle being the mirror image of the other.
Not all fractions appear on the left side of the fold in each cycle (but the missing fractions do appear on the right side of the fold).
Example: p = 31
All fraction pairs are in terms of thirty-oneths. We have
(1, 30) -> (16, 15) -> (8, 23) -> (4, 27) -> (2, 29) -> repeat
(3, 28) -> (17, 14) -> (24, 7) -> (12, 19) -> (6, 25) -> repeat
(5, 26) -> (18, 13) -> (9, 22) -> (20, 11) -> (10, 21) -> repeat
Plus the mirror images starting with (30, 1),(28, 3), and (26, 5).
The fractions pairs break into disjoint circles of equal length. Not all fractions appear, either on the left or on the right of the fold, in each cycle.
Example: p = 17
All fraction pairs are in terms of seventeenths. We have
(1, 16) -> (2, 15) -> (4, 13) -> (8, 9) -> (16,1) -> (15, 2) -> (13, 4) -> (15, 2) -> repeat
(3, 14) -> (6, 11) -> (12, 5) -> (7, 10) -> (14,3) -> (11, 6) -> (5, 12) -> (10, 7) -> repeat
The fractions pairs break into two disjoint circles of equal length. Each fraction that appears in a cycle does so twice, once on each side of the fold. Each cycle is its own mirror image.
Our goal is to classify which primes yield which behavior.
The possible behaviors are:
- Each cycle that appears is its own mirror image. (Each fraction that appears on the left of the fold also appears on the right.)
- No cycle is its own mirror image, but cycles come in pairs with one the mirror image of the other. (Each fraction in a cycle appears only once, on one side of the fold.)
- There is just one cycle, necessarily its own mirror image.
- There are precisely two cycles, one the mirror image of the other.
- There are precisely two cycles, each their own mirror images.
- There are more than two cycles.
Result 2: There is a number N such that 1 = in 2^N in the group {1, 2, ..., p-1}.
Proof: Consider the powers of two: 1, 2, 4,8,16,… . Two elements of this sequence must leave the same remainder upon division by p .Thus there are two powers of two which differ by a multiple of p. Suppose 2^M – 2N = 2^(M-N)(2^N-1) with M > N is a multiple of p . Since p is odd, it follows that 2 1(mod ) N = p .
Set ord_p(2) to be the smallest value of N > 0 such that 2^N ≡ 1(mod p) .
Result 3: If ord_p(2) is even, then there is a value k>1 such that -1 = 2^k in the group {1, 2, ..., p-1}. If ord_p(2) is odd, then there is no value k>1 such that -1 =2^k in {1, 2, ..., p-1}
Proof: Supposed ord_p(2) = 2k. Then 0 = 2^(2k) -1 =(2k +1)(2^k -1) in {1, 2, …, p-1}. Since ord_p(2) is not less than 2k, it follows that 2^k + 1 = 0 in {1, 2, …, p-1}
Suppose ord_p(2) is odd, but -1=2^k {1, 2, …, p-1}. Choose k as small as possible. Then 1=2^(2k) and so ord_p(2) is an odd factor of 2k . So 2^n=1 for some odd factor n of k and so 2^k=1 as well. But −1 ≠ 1 in {1, 2, …, p-1}, giving a contradiction.
With regards to our examples,
For p = 11, we have 1 = 2^10 and -1 = 2^5
For p = 7, we have 1 = 2^3 and -1 is not a power of two.
For p = 31, we have 1 = 2^5 and -1 is not a power of two.
For p = 17, we have 1 = 2^8 and -1 = 2^4.