Author |
Topic: Modular equation (Read 580 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: Modular equation
« Reply #1 on: Feb 11th, 2003, 5:34pm » |
 Quote  Modify
|
I come up with 63 integers. But there is yet a hole in my proof that more integers might possibly slip through:
Proof: 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, m49=0 mod m2, but m != 0 mod m2. So C{m2} is false. It follows that n is square-free (has no square factors).
If p is prime, then Fermat's Little Theorem says rp-1 = 1 mod p for all r not divisible by p. if 48=(p-1)k for some k, then r48=r(p-1)k=1k=1 mod p, and so r49=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 r48=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 r49-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)!).
|
|
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Modular equation
« Reply #2 on: Feb 17th, 2003, 5:08pm » |
Quote Modify
|
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, rk=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 rk=1 mod p. Equivalently, if Zpx, the group of units of the field Zp, 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 m2 | 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! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
