What is the greatest possible positive integer n if 8^n divides (44)^44 without leaving a remainder

The numbers in the sequence

, , , , are of the form , where For each , let be the greatest common divisor of and . Find the maximum value of as ranges through the positive integers.

Solution 1

If

denotes the greatest common divisor of and , then we have . Now assuming that divides , it must divide if it is going to divide the entire expression .

Thus the equation turns into

. Now note that since is odd for integral , we can multiply the left integer, , by a power of two without affecting the greatest common divisor. Since the term is quite restrictive, let's multiply by so that we can get a in there.

So

. It simplified the way we wanted it to! Now using similar techniques we can write . Thus must divide for every single . This means the largest possible value for is , and we see that it can be achieved when .

Solution 2

We know that

and . Since we want to find the GCD of and , we can use the Euclidean algorithm:

Now, the question is to find the GCD of

and . We subtract 100 times from . This leaves us with . We want this to equal 0, so solving for gives us . The last remainder is 0, thus is our GCD.

Solution 3

If Solution 2 is not entirely obvious, our answer is the max possible range of

. Using the Euclidean Algorithm on and yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the term share factors with the . Using the Euclidean Algorithm, . Thus, the max GCD is 401.

Solution 4

We can just plug in Euclidean algorithm, to go from

to to to get . Now we know that no matter what, is relatively prime to . Therefore the equation can be simplified to: . Subtracting from results in . The greatest possible value of this is , an happens when .

See also

1985 AIME (Problems • Answer Key • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

• AIME Problems and Solutions
• American Invitational Mathematics Examination
• Mathematics competition resources

What is the greatest possible integer if 8 n divides 44 44?

How do you find the greatest positive integer?

What is the greatest positive number?

What is the greatest possible positive integer in if 16?