Bunuel wrote:
For positive integers k and n, the k-power remainder of n is defined as r in the following equation:
n = k^w + r, where w is the largest integer such that r is not negative. For instance, the 3-power remainder of 13 is 4, since 13 = 3^2 + 4. In terms of k and w, what is the largest possible value of r that satisfies the given conditions?
A. (k – 1)k^w – 1
B. k^w – 1
C. (k + 1)k^w – 1
D. k^(w+1) – 1
E. (k + 1)k^(w+1) – 1
Kudos for a correct solution.
MANHATTAN GMAT OFFICIAL SOLUTION:We are told that n = k^w + r, with a number of conditions on the possible values of the variables (k and n are positive integers, w is an integer, and r is non-negative). An example is given to us:
13 = 3^2 + 4. The question is this: for a given k and w, what is the largest possible value of r?
Let’s keep with the example. The given k and w are 3 and 2, respectively, in the expression 3^2. The question becomes “how big can r get?” At first, it might seem that there’s no cap on the size of r, but if you consider n = 30, for instance, you can write it using a larger power of 3:
30 = 3^2 + 21
30 = 3^3 + 3
So the first equation doesn’t fit the conditions (w has to be the largest integer such that r is not negative).
The tipping point is the next power of 3, namely 3^3 = 27. 27 itself would be written as 3^3 + 0, with r = 0, so the number that gives the largest r for k = 3 and w = 2 must be 26:
26 = 3^2 + 17, giving r = 17.
At this point, we could take a number-testing approach: which answer choice equals 17 when k = 3 and w = 2? After a little computation, we’d find that the answer is (A).
We can also take a more algebraic approach. The maximum r is going to come when n is the integer just below the next power of k above k^w, in other words when n equals k^(w+1) – 1.
Plug this expression for n into the equation:
k^(w+1) – 1 = k^w + r
Now split k^(w+1) into k*k^w:
k*k^w – 1 = k^w + r
Finally, subtract k^w from both sides:
(k – 1)(k^w) – 1 = r
The left side matches the expression in choice (A).
The correct answer is A.