|
||
|
Title: A Positive Integral Determination Puzzle Post by K Sengupta on Apr 16th, 2006, 8:13am 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. |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by Barukh on Apr 17th, 2006, 3:46am Wow! Is it Medium? |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by jollytall on Apr 17th, 2006, 10:29am 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). |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by Barukh on Apr 17th, 2006, 11:22am I think the statement of the problem excludes any ambiguities, and power of a prime counts as one divisor. Hint: [hide]The answer is Yes.[/hide] |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by jollytall on Apr 17th, 2006, 2:22pm 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. |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by Barukh on Apr 18th, 2006, 9:01am 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: [hide]Try to change your very first formula a bit.[/hide] |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by K Sengupta on May 26th, 2006, 11:27pm 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). |
||
|
Title: Re: A Positive Integral Determination Puzzle Post by Eigenray on May 31st, 2006, 5:57pm on 05/26/06 at 23:27:50, K Sengupta wrote:
You mean: since p | 3Bh(32hBh - 3h+1) + 1, p can't divide 3Bh. (Hence p divides Ah+1 but not Ah.) |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |