Author |
Topic: Integer Count (Read 469 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Integer Count
« on: Sep 25th, 2007, 2:29pm » |
 Quote  Modify
|
For integers m,n m > 2 determine the number of
integers m for which n25 = n (mod m) holds for all
integers n.
|
| « Last Edit: Sep 25th, 2007, 9:51pm by Michael Dagg » |
 IP Logged |
Regards,
Michael Dagg
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Integer Count
« Reply #1 on: Sep 26th, 2007, 11:05am » |
Quote Modify
|
I thought there are 16, but now it seems there are more...
And the question looks much more difficult now.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer Count
« Reply #2 on: Sep 26th, 2007, 11:18am » |
Quote Modify
|
I found 31; looking up to 100000. It seems to stop at 2730
2 3 5 6 7
10 13 14 15 21
26 30 35 39 42
65 70 78 91 105
130 182 195 210 273
390 455 546 910 1365
2730
|
| « Last Edit: Sep 26th, 2007, 11:19am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Integer Count
« Reply #3 on: Sep 26th, 2007, 12:49pm » |
Quote Modify
|
Adding 1, we get 32 = 25. Is this a coincindence?
Note the following properties of the numbers:
| hidden: | 1. They are squarefree.
2. They come in pairs: if an odd number N is on the list, so does 2N.
3. Number 24 plays a central role here. |
|
| « Last Edit: Sep 26th, 2007, 12:51pm by Barukh » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Integer Count
« Reply #4 on: Sep 26th, 2007, 1:26pm » |
Quote Modify
|
Of course this is no coincidence, Barukh, but you knew that.
Here's my thinking:
| hidden: | 1. Any such m must be square-free, since if p^2 divides m, then in particular p^25 - p is not divisible by p^2, and is thus not divisible by m.
2. For any collection of distinct primes, p_i, each of these primes works for m if and only if their product does. This is fairly straightforward since n^25 - n is divisible by each of these primes if and only if it is divisible by their product.
3. Therefore, the problem can be solved by identifying which primes work for m, and then any m must be a square-free product of these primes.
4. If n^25 - n is divisible by a prime p for all n, then this means that n^25 - n = (n)*(n-1)*(n^23 + n^22 + ... + n + 1) is a polynomial with p roots in Z/pZ. Since this polynomial is of degree 25, it cannot have more than 25 roots, and thus p < 25.
5. We can then check primes less than 25 individually and see that 2, 3, 5, 7, and 13 work (but 11, 17, 19, and 23 don't). Fermat's little theorem explains why this will only work if (p-1) divides (25 - 1).
6. Putting these together, we see that any m must be a square-free product of 2, 3, 5, 7, and 13. This yields 2^5 = 32 possibilities, but one of them, the "empty square-free product" of 1, is disallowed by the restriction in the problem that m >= 2. |
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Integer Count
« Reply #5 on: Sep 26th, 2007, 11:20pm » |
Quote Modify
|
Good job, Joe, in putting it all together! 
In fact, I knew this before I read your post, but after I wrote my previous post.
Thanks for this beautiful problem, Michael!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print