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

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

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.

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

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?

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.

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.

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: [4^16] ^ODD + [1] ^ 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 ----- [4^16] ^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-

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

Excellent question!

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.