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 $\displaystyle p^n + p^{n - 1} + ... + 1 = q^2 + q + 1$.

    My idea:

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

    Let k be the largest power of p dividing q+1, then
    $\displaystyle 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 $\displaystyle q+1 = pc$ for some $\displaystyle 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: $\displaystyle 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 $\displaystyle 1+q+q^2 = 1+p+p^2+\ldots+p^{2n} = \frac{p^{2n+1}-1}{p-1}$.

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

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

    $\displaystyle p(p^n+1)(p^n-1) = (p-1)q(q+1)$.

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

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

    If $\displaystyle q=p^n+1$ then $\displaystyle p(p^n-1) = (p-1)(q+1)$, so $\displaystyle p(q-2) = (p-1)(q+1)$ and therefore $\displaystyle 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 $\displaystyle q=p^n-1$ then a similar calculation to the previous paragraph gives $\displaystyle 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, 08:16 AM
  2. Replies: 4
    Last Post: Jan 13th 2010, 06:42 AM
  3. A olympiad question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Sep 30th 2009, 06:43 AM
  4. Tough Problem from an olympiad
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Feb 15th 2009, 05:20 PM
  5. Replies: 21
    Last Post: Nov 11th 2007, 07:20 AM

Search Tags

/mathhelpforum @mathhelpforum