A number 4^16 + 1 is divisible by x. Which among the following is also

Question

A number  4^{16} + 1  is divisible by x. Which among the following is also divisible by x?

A)  4^{96} + 1 
B)  4^{32} + 1 
C)  4^{8} + 1 
D)  4^{48} + 1 
E)  4^{24} + 1

nick1816 · Accepted Answer

a^n+b^n  is divisible by a+b, if n is an odd positive integer.
Only in option D, n is odd

4^{48}+1= (4^{16})^3+(1)^3

Abhishek009 · Answer

Dear the following formulas exisists for numbers divisbility - Capture.PNG

shameekv1989 · Answer

I see 3 properties in GMAT Club Math Book :-

i) a^n - b^n is always divisible by a-b
ii) a^n - b^n is divisible by a+b when n is even 
iii) a^n + b^n is divisible by a+b when n is odd and not divisible by a+b when n is even

Can you confirm about the following :- 
I) is a^n - b^n ever divisible by a+b when n is odd? --> I tried with numbers and I never get this case divisible
II) is a^n + b^n divisible by a-b when n=odd and n=even? --> I tried with numbers and I always get this case divisible

shameekv1989 · Answer

Abhishek009  :- If you consider the following case :-
(a^n + b^n)/(a-b) = (3^3 + 2^3)/(3-2) i.e. if a and b are consecutive numbers then a^n+b^n will always be divisible by a-b.

Archit3110 · Answer

giving a try :

given  4^{16} + 1  is divisible by x
which can be written as ; 
(4^16)^1 = a*x-1
LHS is even so RHS also has to be even which is possible only when a*x is   odd  so the given option would be correct which has base as 4^16 raised to power of  odd number  
eliminate c&e as they dont have base of 4^16
A)  4^{96} + 1  ; (4^16)^6+1 
B)  4^{32} + 1  ; (4^16)^2+1 
D)  4^{48} + 1  ;(4^16)^3+1

option D is valid

ShreyasJavahar · Answer

Hi  nick1816 , in 4^{96}, 96 can be written as (4^{32})^3. Isn't n odd here as well? Can you please explain where I am going wrong?

IanStewart · Answer

That is true, but that only demonstrates that 4^96 + 1 must be divisible by 4^32 + 1, which is not what we want to know here.

The list of rules one or two people posted earlier in this thread all come from algebra. If you have a sum of two cubes, for example, you can factor:

x^3 + y^3 = (x + y)(x^2 - xy + y^2)

If you replace x and y with the numbers 4^16 and 1, you find

4^48 + 1 = (4^16)^3 + 1^3 = (4^16 + 1)(some other integer)

so from there, we see 4^16 + 1 must be a divisor of 4^48 + 1.

But learning this type of thing is, as best I can tell, completely pointless if you're preparing for the GMAT (and in most cases, learning the rules posted above would be pointless too). I have never seen a single official question where you'd need to know how to factor any kind of proper cubic, either with numbers or with letters in it. The factoring patterns you need to know are the basic ones - the difference of squares (which you might need to use with larger powers, e.g. with a^8 - b^8, and often need to use with numbers in place of letters), and the squares, (x + y)^2 and (x - y)^2.

The original question in this thread can't be answered, incidentally, without some information about x. It turn out 4^16 + 1 is prime (it's one of the famous 'Fermat primes', though that's not something you'd ever need to know on the GMAT). So x can only be equal to 1 or to 4^16 + 1. But if x = 1, which is possibly true from the wording of the question, then every answer is correct. It's only if x = 4^16 + 1 that D is the right answer.

ShreyasJavahar · Answer

This certainly cleared things up for me and yes, at least personally, this is very challenging to solve within 2, or perhaps even 3, minutes without being aware of the formulae mentioned above. Thanks.

Fdambro294 · Answer

1st) Factor Foundation Rule: If a Number is Divisible by another Number Y, then that Number is also Divisible by all the Factors of Y.

X is a Factor of (4)^16 + 1. Whichever A.C. is Divisible by (4)^16 + 1 will also be Divisible by X.

2nd) when an Expression is of the Form:

(a)^n + (b)^n ----

RULE: if the N Exponent is ODD ----- the Expression is always divisible by (a + b)

RULE: if the N Exponent is EVEN --- we can not make any conclusions regarding the Divisibility of (a + b) or (a - b)

3rd) when the Expression is of the Form:

(a)^n - (b)^n

RULE: if the N Exponent is ODD ---- then the Expression is always divisible by (a - b)

RULE: if the N Exponent is EVEN ---- then the Expression will always be divisible by BOTH (a + b) and (a - b)

Since we are dealing with the Expression of the type: (a)^n + (b)^n = (4)^16 + (1)^16 ----

Let: (4)^16 + (1)^16 = (a + b)

Which Answer Choice is of the Form: (a)^ODD + (b)^ODD --- such that we are sure that (a + b) is Divisible

in other words, we want the A.C. to be of the Following Form:   ^ODD +   ^ ODD

Since the Base of 1 to any (+)Pos. Integer Exponent will always have the Same Result = 1

the question essentially comes down to the following:

?Which A.C. can we express the Base of 4 as -----   ^ODD EXPONENT?

that A.C. will be Divisible by 4^16 + 1 ---- as well as --- X

-A-

(4^16) ^6 + (1) ^6

we can not make any determinations whether (a + b) = (4'16 + 1) is a Factor because the Exponent = EVEN

-B-

(4^16)^2 + (1)^2

same logic as Answer -A-

-D-

(4^16)^3 + (1)^3 = 4^48 + 1

Since the Expression in A.C. -D- is of the form: a^n + b^n ---- in which the Exponent = 3 = ODD

We can say with certainty that (a + b) = 4^16 + 1 is Divisible into Answer D

therefore, Any Factors such as X will also be Divisible into Answer D

Answer -D-

ScottTargetTestPrep · Answer

Solution:

Since x^3 + y^3 = (x + y)(x^2 - xy + y^3) and letting x = 4^16 and y = 1, we see that:

x^48 + 1 = (x^16 + 1)(x^32 - x^16 + 1)

Since x^16 + 1 is divisible by x, x^48 + 1 is also divisible by x.

Answer: D

EatMyDosa · Answer

Excellent question!

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

A number 4^16 + 1 is divisible by x. Which among the following is also

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

A number 4^16 + 1 is divisible by x. Which among the following is also

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards