Lemma 1 is trivial. Regardless of the value of
θ, if every digit in the starting string is the same, then the only permutation is the identity permutation, which entails m = n. Thus, n - m = 0, and
(ϕ−1) divides zero evenly because every number other than zero divides zero evenly.
Corollary 1a. The proposition is true if
θ = 1 because a string with only one digit has no permutation except the identity permutation.
Corollary 1b. There exists at least one integer
≥ 1 for which the proposition is true. Let k be an arbitrary one of those integers. In other words, given a starting string of k digits, the difference between the number represented by that string and the number represented by any permutation of that string is evenly divisible by
(ϕ−1).
Now we consider the case where
θ = k + 1
≥ 2. Obviously, if all (k + 1) digits are the same, Lemma 1 applies. So we restrict attention to those cases where at least two digits differ. That entails that one digit in the starting string differs from the high order digit in the starting string. We start with another special case, namely permutations where the high order digit stays the same, to get Lemma 2.
n=a1∗ϕ{(k+1)−1+i=1∑kai+1k∗ϕ(k−i)=a1ϕk+b.m=a1ϕk+c, where c is represented by an arbitrary permutation of the string representing b.(n−m)=(a1ϕk+b)−(a1∗ϕk+c)=b−c.b is represented by a string of kdigits, and c is represented by a permutation of b.∴ ∃ integer j such that (b−c)=(ϕ−1)∗j by Lemma 2.∴n−m=b−c⟹n−m=(ϕ−1)∗j⟹(ϕ−1) ∣ (n−m) ∵ j is an integer.
Lemma 2 does not directly help us because it covers only those permutations that do not affect the high order digit. So let’s consider another special case, namely one where the permutation leaves in their original position all digits in the starting string except the high order digit and one arbitrary digit that differs from the high order digit. In short, we are considering the special case where the permutation only swaps the high order digit and one digit of a different value. We do not know where this arbitrary different digit may lie in the string so we say it is in the wth position going left to right. All we know is that w is an integer and that 1 < w < k+2. This gives us Lemma 3.
n=i=1∑k+1aiϕ{(k+1)−i}⟹m=n+(awϕk−a1ϕk)+(a1ϕ{(k+1)−w}−awϕ{(k+1)−w})=n+(aw−a1)−aw)((ϕk−ϕ{(k+1)−w})=n+(ϕ(w+1)−1)∗ϕ{(k+1)−w}(aw−a1)=n+(ϕ(w+1)−1(w+1))∗an integer=n+(ϕ−1)∗(i=1∑wϕ{(w+1)−i})∗an integer=n+(ϕ−1)∗an integer.∴ n−m=n−n−(ϕ−1)∗an integer =(ϕ−1)∗an integer⟹(ϕ−1) ∣ (n−m).
Once again, Lemma 3 does not get us home. We have dealt with all permutations that leave the high order digit alone. And we have dealt with any permutation that swaps the high order digit and a single digit that differs from the high order digit but is otherwise arbitrary. Let’s name as p an arbitrary example of one of those permutations of n. Now leaving the high order digit of p alone, let q be an arbitrary permutation of the low order digits of p. This gets us Lemma 4.
∃ integer u such that n−p=(ϕ−1)u by Lemma 3.∃ integer v such that p−q=(ϕ−1)v by Lemma 2.n−q=n−p+p−q=(n−p)+(p−q)=(ϕ−1)u+(ϕ−1)v=(ϕ−1)(u+v).∴ (ϕ−1) ∣ (n−q).
But lemmas 2 and 4 cover all the permutations possible in a string of k+1 digits.