Author |
Topic: A Positive Integral Determination Puzzle (Read 535 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A Positive Integral Determination Puzzle
« on: Apr 16th, 2006, 8:13am » |
 Quote  Modify
|
Determine whether or not there exists a positive integer n such that n is divisible by exactly 2005 different prime numbers and (2^n + 1) is divisible by n.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Positive Integral Determination Puzzle
« Reply #1 on: Apr 17th, 2006, 3:46am » |
Quote Modify
|
Wow! Is it Medium?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: A Positive Integral Determination Puzzle
« Reply #2 on: Apr 17th, 2006, 10:29am » |
Quote Modify
|
Well, not for me! Some early thoughts:
I hoped to prove that if it has more than 1 prime divider then it is already impossible. But it is not the case.
n=3*3*19 is a good example. I do not know though, if it is correct for 2 dividers or not? I think yes, but "exactly" in this context is a tricky word. We should agree, whether one prime can be repeated or not (albeit the final result might be the same in both cases).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Positive Integral Determination Puzzle
« Reply #3 on: Apr 17th, 2006, 11:22am » |
Quote Modify
|
I think the statement of the problem excludes any ambiguities, and power of a prime counts as one divisor.
Hint: The answer is Yes.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: A Positive Integral Determination Puzzle
« Reply #4 on: Apr 17th, 2006, 2:22pm » |
Quote Modify
|
Well, from the word "different", it was clear to me that 3*3*19 cannot be the solution to "divisible by exactly 3 primes". The question was for me (now I guess answered), whether it is a solution for 2.
I could understand the sentence two ways: Number n, when written up as a product of primes - 2*2*3*3*... - it has altogether exactly 2005 elements and all are different OR it has any number of elements in the list but those are from exactly 2005 different value. With other words, is it allowed to have a prime on a power 2 or more?
If it is allowed - and Barukh's post tells me that - then I have a sort of a solution, though not yet proven (so I don't hide):
Step 1: Let's take numbers that are 2*3^x+1. E.g. 3, 7, 19, 55, 163, 487, 1459, 4375, 13123, 39367, etc. First thought that there are infinite of these that are prime: 3, 7, 19, 163, 487, 1459, 39367, etc. It should be proven though, but if:
Step 2: For every such prime we say n=p*m. 2^n=2^(p*m)=(2^p)^m. 2^p=2 mod p, so 2^n=2^m mod p. We look for those m-s, where 2^m+1=0 mod p. I found that for many of these primes (actually for all where there is a solution for m) m=(p-1)/2 + k*(p-1), where we also know from the previous step, that (p-1)/2=3^x. The first few such primes are: 3, 19, 163, 1459, 86093443. The m of the largest (43046721 in this case) is also a good m for all the smaller p-s. So what is missing from this step is that from these p primes also infinite has an m as above (not all though, e.g. 7, 39367).
Step 3: Now we have p1, p2, p3, etc. and the largest m (=3^x). We know that for all the pi-s if we take n=pi*m then 2^n+1=0 mod pi. I also found that n=pi*pj*m is also a solution for 2^n+1=0 mod both pi and pj, or even any number of pi-s. This has to be proven again, though.
If these are all correct then we have to take the first 2005 (or number 3 and 2004 other such) primes and n=p2*p3*...*p2004*m is the solution (p1=3 is included in m). This n has 3 on a high power, all other primes only once.
For the first few it is:
N=3, 171, 250857, 3294003267, 16745828880090373214769
This is how far I could get. Still a lot to be proven, but it seems to work.
If the primes cannot be on a higher power then I do not see the solution.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Positive Integral Determination Puzzle
« Reply #5 on: Apr 18th, 2006, 9:01am » |
Quote Modify
|
Very nice analysis, jollytall, and you are on the right track. In fact, the solution is easier and doesn' t require proving any unfamiliar theorems on primality.
Hint: Try to change your very first formula a bit.
|
|
IP Logged |
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: A Positive Integral Determination Puzzle
« Reply #6 on: May 26th, 2006, 11:27pm » |
Quote Modify
|
I furnish hereunder the texts constituting the solution to the problem under reference.
Note that for any given odd B, we have:
2^(AB) + 1 = (2^A + 1)(2^(A(B-1)) -2^(A(B-2)) + …….+1 )
and, so 2^A + 1 is a factor of 2^(AB) + 1. Accordingly, it is sufficient to find m such that:
(I) m possesses only a few distinct prime factors.
(II) 2^m + 1 has a large number of distinct prime factors.
(III) m divides 2^m + 1. For then, we can take k, a product of enough distinct primes dividing 2^m + 1 ( but not m), so that km has exactly 2005 factors. Then km still divides 2^m +1. and hence 2^(km) + 1.
The simplest case is where m has exactly one distinct prime factor p, in other words, it is a power of p. but if p is a prime, then p divides (2^p -2). So the only p for which p divides (2^p +1) is 3. So the questions are:
(i) Whether Ah = (2^m + 1) is divisible by m = 3^h, and
(ii) Ah has a large number of distinct prime factors.
Consider, A(h+1) = Ah(2^2m - 2^m +1), where m = 3^h.
But 2^m = Ah - 1, so A(h+1) = Ah(Ah^2 – 3*Ah + 3). Now, A1 =9. So an induction shows that 3^(h+1) divides Ah, which answers (i) affirmatively.
Also, since Ah is a factor of A(h+1), any prime dividing Ah also divides A(h+1).
Substitute Ah ={3^(h+1)}*Bh. This gives:
B(h+1) = Bh*{(3^(2h + 1)*(Bh^2) – 3^(h+2)*Bh + 1}.
Now, obviously 3^(2h + 1)*(Bh^2) – 3^(h+2)*Bh + 1 is greater than one, so it must necessarily possess some prime factor p greater than 1.
Since 3^(2h + 1)*(Bh^2) – 3^(h+2)*Bh + 1 is a multiple of (3*Bh +1), it follows that p is equal to3 or p divides Bh. So, B(h+1) has at least one prime factor p greater than 3 which does not divide Bh. So B(h+1) has at least h distinct prime factors greater than 3, which answers (ii) affirmatively. Consequently, without any loss of generality, we can take m = 3^2005.
Consequently, we observe that:
(A) m possesses only one distinct prime factor.
(B) (2^m + 1) = (3^2006)*B(2005) has at least 2004 distinct prime factors other than 3.
(C) m divides (2^m +1).
Take k to be the product of 2004 distinct prime factors dividing B(2005).
Then n =k*m is the required number with exactly 2005 distinct prime factors which divides (2^n + 1).
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A Positive Integral Determination Puzzle
« Reply #7 on: May 31st, 2006, 5:57pm » |
Quote Modify
|
on May 26th, 2006, 11:27pm, K Sengupta wrote:| Since 3^(2h + 1)*(Bh^2) – 3^(h+2)*Bh + 1 is a multiple of (3*Bh +1), it follows that p is equal to3 or p divides Bh. |
|
You mean: since
p | 3Bh(32hBh - 3h+1) + 1,
p can't divide 3Bh. (Hence p divides Ah+1 but not Ah.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print