This one, by Dr. Titu Andreescu (of USAMO fame), is elementary in the sense that the solution to the problem doesn’t require anything more than arguments involving parity and congruences. I have the solution with me but I won’t post it on my blog until Jan 19, 2008, which is when the deadline for submission is. By the way, the problem (in the senior section) is from the 
Problem: Find the least odd positive integer 
11 comments
Comments feed for this article
January 7, 2008 at 4:08 pm
music
very interesting.
i’m adding in RSS Reader
January 17, 2008 at 3:09 am
John smith
I started with p=2 to see what happens. I also assumed that if i find the least value n, it would be valid for all P but of course this could be false.
I found that n must satisfy n(n+1) such that there are at least 3 unique prime factors and that 2n+17 must also contain these factors.
is that right ? not sure how to find n or why if i do it should be divisible by at least four (distinct) primes for ALL P though.
January 17, 2008 at 3:35 am
Vishal
Hint:
——-
Since n is an odd positive integer, let n = 2k+1, where k is some non-negative integer. Plug this back into the expression E, and simplify E. This helps to get rid of the 4 in the denominator.
Now, plug p=2, and try a few (small) values for k, and determine the smallest value of k for which E is a product of 4 prime numbers. This helps to determine the smallest n because n = 2k+1.
Now, argue that for all odd primes p, the smallest value of n you found out above always makes E an integer which is divisible by four prime numbers. (This is non-trivial and requires some effort.)
One last hint:
—————–
Work with small prime numbers in the last case above.
January 17, 2008 at 8:15 pm
John smith
the only other clue is that E is divisble by 4 primes when p=2 and 5 when p>2?
the trouble is i dont know how to determine the smallest value of k for which E is a product of 4 prime numbers.
I got n(n+1)=2^a.p^b.q^c.r^d where p,q,r are prime and therefore 16(2n+17)= some powers of (2.p.q.r )
I tried combinations like 2.3.5.7 but it fails.
January 17, 2008 at 8:54 pm
Vishal
Okay, we let n = 2k+1.
Now for p=2, plug k=0,1,2,… (a few values) and determine the (smallest) value of k which ensures that E is product of four primes. (k is a small number.)
Now, for p > 2, plug the above value of k (you found above) back into E, and tell me what your expression E (only in terms of p) is.
January 18, 2008 at 3:29 am
John smith
E=30+11p^4+p^8
But I’ve got a few questions:
Firstly how did you get the value n=11 by sheer trial and error?
Secondly at this point do we just instinctively make a conjecture that n=11 is the smallest and go from there?
January 18, 2008 at 4:28 am
Vishal
I didn’t get n=11 as the least odd integer for this problem. The least n is slightly less than 11.
Yes, you kinda make a conjecture (or hope) that the smallest n obtained for p=2 will also work for bigger primes p.
I would also like to make a small addition to the hints I provided earlier. Verify that the smallest n you got earlier also satisfies the conditions of the problem for p=3.
And, then for all primes p > 3, you argue in a general way that the smallest n indeed satisfies the conditions of the problem once again. Here, you will have to again make some conjectures about what primes will always be factors of E for p > 3. Without guessing what primes p will be factors of E, the problem will be almost impossible to solve.
Lastly, making conjectures is an important part of mathematical activity. I think you probably don’t like it
January 18, 2008 at 7:53 pm
John smith
n=9
January 18, 2008 at 8:00 pm
John smith
it may or may not be relevant here but is there a better way to find all n such that E for a given value,p, is divisble by 4 primes than trial error?
January 18, 2008 at 8:01 pm
John smith
why do you think i dont like it?
January 18, 2008 at 10:21 pm
Vishal
You are right about n=9. You are half-way through the solution!
I don’t have a way to find all n such that for a given prime p, E is divisible by at least four primes. If there is one, then finding the same is going to be quite difficult, I think. But, yeah, that would certainly be a good problem!
The reason I said you may not like the idea of making conjectures in this problem is at some level doing so “diminishes” the elegance of the solution. That’s my guess, and I could be very wrong.