Anonymous Wrote:I took this from an explanation from the Official Guide (don't worry I won't post the actual problem).
The explanation states that "because x^3 is divisible by 9, x must be divisible by 3".
Why is this true?
My assumption was that, since 3^2 is a factor of x^3 (and x is the only source of factors), then 3 must be a factor of x. But does this ALWAYS hold true? Can you say, since x^9 is divisible by 9, than x must be divisible by 3?
Thanks,
mdh
yes, on all counts. in fact, it doesn't even have to be 9; even if all we know is that x^n (for any n
> 1) is divisible by 3, that's enough to deduce that x is divisible by 3.
the reason is because x^n is the product of n identical "x"s, each of which has the same prime factors. therefore, for any given prime factor, there are only two choices:
* that prime factor appears in the prime factorization of x (and thus appears in x^n at least n times)
* that prime factor doesn't appear in the prime factorization of x (and thus doesn't appear in x^n at all)
if there are any 3's in the prime factorization of x at all, then that means 3 goes into x, which means that the prime factorization of x^n actually contains at least n "3"s.
note that this only HAS to be true for PRIME numbers, though. for composite numbers, it may or may not be true.
for instance, if you know that x^3 is divisible by 64, it does NOT follow that x is divisible by 8. however, if x^3 is divisible by 16, then x DOES have to be divisible by 4. (see if you can work out the details; if not, post back)