Ponder This Challenge - April 2005 - Divisibility of integer powers

Ponder This Challenge:

Puzzle for April 2005

This month's puzzle is sent in by Max Alekseyev. It appeared in a
Russian mathematics olympiad for university students.
It was originally due to Marius Cavache.

We are not asking for submission of answers this month.

Problem:

"b^k" denotes b raised to the k power.

Let a,b be integers greater than 1. Clearly if b=a^k for some positive
integer k, then ((a^n)-1) divides ((b^n)-1) for each positive integer n.
Prove the converse: If ((a^n)-1) divides ((b^n)-1) for each positive
integer n, then b=a^k for some positive integer k.

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Answer:

  Click here to download the pdf solution for April's puzzle.

  This puzzle was originally due to Marius Cavache; it appeared as exercise 10674 in the American Mathematical Monthly (vol.107, Aug.-Sept. 2000, p. 654).An alternate proof appears at http://www.mathlinks.ro/Forum/topic-4556.html

Solvers