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 issue of Mathematical Reflections, 2007.

**Problem:** Find the least odd positive integer such that for each prime is divisible by at least four (distinct) primes.

### Like this:

Like Loading...

*Related*

## 11 comments

Comments feed for this article

January 7, 2008 at 4:08 pm

musicvery interesting.

i’m adding in RSS Reader

January 17, 2008 at 3:09 am

John smithI 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

VishalHint:

——-

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 smiththe 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

VishalOkay, 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 smithE=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

VishalI 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 smithn=9

January 18, 2008 at 8:00 pm

John smithit 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 smithwhy do you think i dont like it?

January 18, 2008 at 10:21 pm

VishalYou are right about

n=9. You are half-way through the solution!I don’t have a way to find

allnsuch that for a given primep,Eis 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.