Conference rusure::math

I can give you a partial answer, which I think generalizes, although I
can't prove it:  If M is prime, talking odd powers generates permutations
if and only if M = 2^k + 1.

Proof:  All powers of 0 are 0, so let's just ignore 0 for the moment.
Now, the M-1 non-zero integers {1,...,M-1} form a multiplicative group, using
multiplication mod M.  (If M-1 isn't a prime, this doesn't produce a group
since the product of two numbers in {1,...,M-1} equals M, which is 0 mod M.)
Call this group G.

Now, let r be any odd number; the map f(x) = x^r is a homomorphism of G to
itself.  It generates a permutation exactly when it is onto.  However, G is
finite, so it's just as good to show that f is 1-1.  Since f is a homomor-
phism, we need only show that its kernel is exactly {1}.

Suppose M is prime and one more than a power of 2.  We have come down to
showing that x^r <> 1.  We know the ker f is a subgroup of G.  Since the
only divisors of #G = 2^k are even numbers, ker f is of even order (or unit).
However, anything in ker k, if raised to the r'th power, is 1, so
#(ker f) | r.  However, this is only possible for #(ker f) = 1.

Conversely, suppose M is prime but NOT a power of 2.  Then it has odd factors,
and so G has SOME odd-order subgroup H.  (You can use the Sylow theorem if
you really want, although that's way too strong.)  Let h = #H; h is odd.  If
x is in H, x <> 1, then x^h = 1 ==> x in ker f, f(x)=x^h; so x^h does NOT
generate a permutation.  QED

If M is NOT prime, G isn't a group (since it has "0-divisors" in the form of
all factors of M).  Hence, we don't get to apply all the fancy group-theoretic
machinery quite so easily.  Nevertheless, I believe a similar proof can be
made to go through, though I haven't done it; we've really used only some very
general facts about groups; some in fact are true of arbitrary catagories.

So...conjecture:  The maps under consideration are all permutations exactly
when M is of the form 2^k+1.  Further, any odd divisor of M-1 is a counter-
example.
							-- Jerry

Congratulations, Jerry!

Unfortunately, the conjecture is false.  The simplest counter-examples
are M = 1, 2, and 10.

		  !  p
	x^p mod 2 ! 1  2
	----------+-----
	   x	0 ! 0  0
		1 ! 1  1

		   !              p
	x^p mod 10 ! 1  2  3  4  5  6  7  8  9 10
	-----------+-----------------------------
		0  ! 0  0  0  0  0  0  0  0  0  0
		1  ! 1  1  1  1  1  1  1  1  1  1
		2  ! 2  4  8  6  2  4  8  6  2  4
		3  ! 3  9  7  1  3  9  7  1  3  9
		4  ! 4  6  4  6  4  6  4  6  4  6
	   x	5  ! 5  5  5  5  5  5  5  5  5  5
		6  ! 6  6  6  6  6  6  6  6  6  6
		7  ! 7  9  3  1  7  9  3  1  7  9
		8  ! 8  4  2  6  8  4  2  6  8  4
		9  ! 9  1  9  1  9  1  9  1  9  1

Hmm.. for some reason, I read the original problem as requiring M to be odd;
however, it doesn't matter.

I mentioned this to a friend who hacks around with this sort of stuff, and
his conjecture - which he was somewhat confident of, although we didn't
sit down to try to prove it - is:  You get permutations mod M iff phi(M)
is a power of 2, where phi is the Euler phi function (phi(M) = number of
number 1<=n<M relatively prime to M).  Not that when M is prime, phi(M)=M-1,
which is consistent with the proof I gave.^(NOTE)

BTW, this stuff is not without some interest, although I've never seen exactly
this question posed:  The integers relatively prime to N, mod N, as a multipli-
cative group, show up in all sorts of recent work on cryptography - such as the
RSA scheme, for one.  (This is clear when you think about what RSA is doing a
bit.)
							-- Jerry

Don't know why I didn't think of this right away, but...  Consider the non-prime
case, numbers mod M.  Let A be {0,...,M-1}.  We can partition A into two pieces,
U = {x in A, (x,M) = 1}, and Z = {x in A, (,M) <> 1}; U and Z stand for Units
and Zero-divisors.  Let f:A -> A be given by f(x) = x^k, some odd k.  Note
the following facts:

1)  U is a group under multiplications.
2)  #U = phi(M) (Euler phi function)
3)  f|U:U -> U; f|Z:Z -> Z - i.e. f preserves the partitioning.

4)  f|U is a group homomorphism (using the multiplicative group structure on
U).

Hence, the arguments of .1 apply to f|U.  However, as in .1, f is onto iff it
is 1-1, and f cannot be 1-1 unless f|U is.  Hence,a NECESSARY condition for all
such f's to be permutations is that #U be a power of 2.

Further, we now know that any f possible under this constraint can only fail on
Z.  I don't know what a sufficient condition for it it work on Z is, although
I still suspect that these don't work very often...
							-- Jerry

66.1:
	If M is prime, talking odd powers generates permutations
	if and only if M = 2^k + 1.

	Note that if M = 2^k + 1 is prime, then k = 2^n.

66.3:
	You get permutations mod M iff phi(M) is a power of 2, where phi is the
	Euler phi function (phi(M) = number of number 1<=n<M relatively prime
	to M).

	This is only partly true.  You don't get permutations for M=2^n (n>1),
	even though phi(2^n)=2^(n-1).


The following are the only M <= 1542 for which you get permutations:

	1,2,3,5,6,10,15,17,30,34,51,85,102,255,257,510,514,771,1285,1542

This leads to two reasonable conjectures:

Conjecture #1:
	You get permutations iff M is a product of unique primes
	of the form (2^k+1).  Or, restated:
	You get permutations iff M is either a product of unique primes
	of the form 2^(2^n)+1, or twice such a product.

Conjecture #2:
	You get permutations iff M is either a product of unique numbers
	of the form 2^(2^n)+1, or twice such a product.

re:  Conjectures.  When I first started playing with this, I got some stuff that
seemed to point to it being important for M to be square-free, which is what
you are proposing.  I don't remember off-hand wexactly where this came up,
but it appears when you try some variation of the group-theoretic argument
of .1.

Question - it's too late at night to think about it - are square-free numbers
with factors of the form of the Conjectures exactly the square-free numbers
with phi = 2^k?  (Note that, by .4, if the conjectures are true, the numbers
MUST have phi's of the right form...)
							-- Jerry