wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Modular equation
        
(Message started by: NickH on Feb 11^th, 2003, 2:49pm)

Title: Modular equation
Post by NickH on Feb 11^th, 2003, 2:49pm

For how many integers n > 1 is r⁴⁹ = r (mod n) true for all integers r?

Title: Re: Modular equation
Post by Icarus on Feb 11^th, 2003, 5:34pm

I come up with [hide]63[/hide] integers. But there is yet a hole in my proof that more integers might possibly slip through:

Proof: [hide] Call the condition C{n}. if C{n} and m|n, then it is easy to see that C{m}, so we look for possible factors of n.

For any m>1, m⁴⁹=0 mod m², but m != 0 mod m². So C{m²} is false. It follows that n is square-free (has no square factors).

If p is prime, then Fermat's Little Theorem says r^p-1 = 1 mod p for all r not divisible by p. if 48=(p-1)k for some k, then r⁴⁸=r^(p-1)k=1^k=1 mod p, and so r⁴⁹=r mod p. If p divides r, then both sides are =0 mod p. So if (p-1)|48, C{p} holds. The primes one higher than a divisor of 48 are 2, 3, 5, 7, 13, 17.

Here is the hole: I believe, but have not been able to confirm, that these are the only primes for which C{p} holds. If gcd(48,p-1) = 1, then it is not hard to see that r⁴⁸=1 mod p ==> r=1 mod p, so C{p} is false. But I have not yet seen what happens when 1 < gcd(48,p-1) < p-1.

Assume that 2,3,5,7,13,17 are the only primes for which C{p} holds. The only other possibilities are the square-free products of these primes. If n=pqr...s, a product of distinct primes, and all of p, q, r,...s divide k, then n|k as well. Thus any product n of the primes above must divide r⁴⁹-r. And so C{n}.

How many such products are there?
c(6,1) + c(6,2) + c(6,3) + c(6,4) + c(6,5) + c(6,6) = 63.
(c(a,b) = a choose b = a!/b!(a-b)!).
[/hide]

Title: Re: Modular equation
Post by Icarus on Feb 17^th, 2003, 5:08pm

I've been trying to close the hole, but I still come up shy. For any prime p other than those listed to satisfy C{p}, it has to be that there is a k such that for all r not divisible by p, r^k=1 mod p. k must also divide both (p-1) and 48.

The result will follow if it can be shown that p-1 is the lowest exponent k such that r^k=1 mod p. Equivalently, if Z_p^x, the group of units of the field Z_p, is cyclic. I am pretty sure that this is the case but have not found a proof, either on my own or by the sources I have checked. I can show it if p-1 is square-free, since for any square-free number there is only one abelian group with it as the order.

It's the remaining cases (there is an m such that m² | p-1 ) that I have not yet found a solution to.

Does anyone know how to prove this? It's been driving me crazy all weekend! ???