Results 1 to 2 of 2

Thread: Olympiad Problem- I am stuck

  1. #1
    Lord of certain Rings
    Isomorphism's Avatar
    Dec 2007
    IISc, Bangalore

    Olympiad Problem- I am stuck

    Find all primes p,q and even n>2 such that p^n + p^{n - 1} + ... + 1 = q^2 + q + 1.

    My idea:

    p(p^{n - 1} + ..... + 1) = q(q + 1).

    Let k be the largest power of p dividing q+1, then
    p^{n - 1} + ..... + 1 = qcp^{k - 1}
    If k>1 then the RHS is divisible by p and LHS is not(I am using n>2)
    so q+1 = pc for some c \in \mathbb{N}

    It looks like I have deduced something, but then what do we do??
    Or is this approach useless??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Aug 2007
    Leeds, UK
    There is only one solution: 2^4+2^3+2^2+2+1 = 5^2+5+1.

    Here's a somewhat messy proof (I'm sure that a number theorist could come up with a better one).

    I'll write 2n in place of n, just to keep track of the fact that n is even. So p and q are primes, and 1+q+q^2 = 1+p+p^2+\ldots+p^{2n} = \frac{p^{2n+1}-1}{p-1}.

    Therefore p^{2n+1}-1 = (1+q+q^2)(p-1),

    p^{2n+1}-p = (q+q^2)(p-1),

    p(p^n+1)(p^n-1) = (p-1)q(q+1).

    Thus q divides p^n\pm1, say p^n+\epsilon = kq, where \epsilon=\pm1 and k\geqslant1. Then p(p^n+1)(p^n-1) = p(kq)(kq-2\epsilon) and so kp(kq-2\epsilon) = (p-1)(q+1).

    But kp > p1 and therefore kq-2\epsilon<q+1, so that (k-1)q < 1+2\epsilon\leqslant3. This is only possible if k=1. Therefore q=p^n\pm1.

    If q=p^n+1 then p(p^n-1) = (p-1)(q+1), so p(q-2) = (p-1)(q+1) and therefore q=3p-1. If p is odd then this means that q is even, which is not possible since q is clearly greater than p. Therefore p=2 and q=5.

    If q=p^n-1 then a similar calculation to the previous paragraph gives p=-q-1 which is obviously impossible.

    So the only solution is p=2, q=5.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chessboard problem. Olympiad question.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Mar 10th 2012, 09:16 AM
  2. Replies: 4
    Last Post: Jan 13th 2010, 07:42 AM
  3. A olympiad question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Sep 30th 2009, 07:43 AM
  4. Tough Problem from an olympiad
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Feb 15th 2009, 06:20 PM
  5. Replies: 21
    Last Post: Nov 11th 2007, 08:20 AM

Search Tags

/mathhelpforum @mathhelpforum