vittalgmat wrote:x and y are positive integers. Is x^16 - y^8 + 345y^2 divisible by 15?

1. x is a multiple of 25 and y is a multiple of 20
2. y = x^2

[spoiler]OA: B[/spoiler]

I took more than 2 mins to solve this. I am interested in different/ faster approaches to this problem.


thanks

Is it divisible by 15? This is just asking: is it divisible by both 3 and 5. Those are easy things to check, at least when given a number.

345 is divisible by 3 and 5 (add the digits to check for 3), so 345y^2 is certainly divisible by 15. So all we need to know is whether x^16 - y^8 is divisible by 15 (since, if you add multiples of 15, you're guaranteed to get another multiple of 15, and if you add a multiple of 15 to something which is not a multiple of 15, you are guaranteed not to get a multiple of 15 - this is an elementary fact of number theory, but a very useful one to understand well for many questions, and of course this is true for any number, not only 15).

Statement 2 is quick to check, as pointed out above- x^16 - y^8 is equal to zero, so sufficient.

As for Statement 1, x and y could each be multiples of 15 (x could be 3*25 and y could be 3*20, for example), so it's certainly possible that x^16 - y^8 is a multiple of 15. But, x could be a multiple of 15 and y might not be (x could be 3*25 and y could be 20), in which case x^16 - y^8 will not be a multiple of 15. So insufficient.

cramya wrote:Hi Ian,
Thank you!

Question:


If individually x^16, y^8 are both divisible by 15 then the combination x^16-y^8+345y^2 is divisible by 15. (someone correct me here if I am mistaken)

Is this correct or am I mistaken?

Also lets say for some reason we find y^8 to be never be divisible by 15 can we for sure say the expression will not be divisible by 15?

What are the norms/rules when there are individual components like these in an expression and the question of divisibility by a number comes in to play?

Please advice.

If you add two (or more) multiples of 15, you'll always get a multiple of 15. Say x and y are multiples of 15. Then we can write:

x = 15a for some integer a
y = 15b for some integer b

so x+y = 15a + 15b = 15(a+b), and we see that x+y is a multiple of 15.

On the other hand, say x is a multiple of 15, and z is not - say z gives a remainder of r when we divide by 15. Then we can write:

x = 15a
z = 15q + r

so x+z = 15a + 15q + r = 15(a+q) + r, and we see that we will get a remainder of r when we divide x+z by 15.

What if we add two numbers, neither of which is a multiple of 15? Here you'd need more information to say anything. We can, as above, write our numbers:

w = 15Q + R
z = 15q + r

and w+z = 15(Q + q) + R + r, but here, R+r might be a multiple of 15, so it's possible that w+z is a multiple of 15, possible that it's not.

And of course you can replace 15 throughout the above with any positive integer 2 or larger.