Tricki

## Revision of Elementary examples of invariants from Fri, 03/04/2009 - 09:28

### Quick description

If you want to show that one object cannot be transformed into another in a given way, then associate a quantity with each object that does not change when you transform objects in the given way, but which is different for the two objects in question.

Very few.

### Example 1

You are given the number 4 and asked to transform it into the number 6. There are three operations that you are allowed to perform: you can replace by , , or Is it possible to convert 4 into 6 by repeatedly applying these operations (in whatever order and for however long you like)?

If you try this, you may eventually become convinced that it is not possible. But how can one prove that it is impossible? One answer is to try to find some property that 4 has but 6 lacks, and to show that one cannot get rid of that property using any of the three operations that you are allowed.

If you are used to this kind of problem with the integers, then one of the first things you will try is modular arithmetic. The idea to find some number and look at what happens mod when one performs the three operations. The smaller is, the easier this will be to investigate, so let us work upwards.

If we take , then we are simply looking at whether a number is even or odd. Since subtracting 49 changes the parity of a number, we will not be able to draw any conclusions. A similar argument shows that taking is no help: to subtract 49 is to subtract 1 mod 3, so one can get any number mod 3 by repeated subtractions of 49.

After these two examples, it starts to become obvious that the smallest number that has any chance of telling us something useful is 7. So let us see what happens when Now we have "neutralized" the operation of subtracting 49 – it makes no difference mod 7, and this is exactly the kind of thing we want to happen. But what happens if we replace by or ?

Let us investigate this in the crudest way possible, by just listing the values of and as goes from to We get for the squares and for the values of . None of these values is equal to 6, so our problem is solved: if we start with 4, then the only numbers we will ever be able to produce are numbers that are equal to 1, 2 or 4 mod 7. (We cannot get , since the only way we have seen of producing is to square , so if we start with a number that is not a multiple of then we will never obtain a multiple of .)

A slightly more sophisticated way of expressing this proof is to say that our three operations always take quadratic residues to quadratic residues. This is obvious for the first two operations, and true also for the third because is a quadratic residue mod .