Divisibility Quant Review (#169)

DCS80 wrote:If n is a positive integer and n2 is divisible by 72, then the largest positive integer that must divide n is:

a)6
b)12
c)24
d)36
e)48


answer later

Picking Number Approach:
Least possible value of n² such that n² is divisible by 72 is 72*2 = 144
Hence, minimum possible value of n = 12.
Largest possible integer that divides n is 12.


Algebraic Approach:
n² is divisible by 72
Hence we can write n² as 72k, where k is an positive integer.
Now, n = √n² = √(72k) = √[(2)*(36)*k] = 6√(2k)
Now for n to be an integer, k must be an even multiple of a perfect square.
Hence, we can write k = 2m², where is a positive integer.
Now, n = 6√(2k) = 6√(2*2*m²) = 12m

Hence, largest possible integer that divides n is 12


The correct answer is B.

DCS80 wrote:If n is a positive integer and n2 is divisible by 72, then the largest positive integer that must divide n is:

a)6
b)12
c)24
d)36
e)48

We are given that n^2/72 = integer or (n^2)/(2^3)(3^2) = integer.

However, since n^2 is a perfect square, we need to make 72 or (2^3)(3^2) a perfect square. Since all perfect squares consist of unique primes, each raised to an even exponent, the smallest perfect square that divides into n^2 is (2^4)(3^2) = 144.

Since n^2/144 = integer, then n/12 = integer, and thus the largest positive integer that must divide n is 12.

Answer: B

DCS80 wrote:If n is a positive integer and n2 is divisible by 72, then the largest positive integer that must divide n is:

a)6
b)12
c)24
d)36
e)48


answer later

---------------ASIDE #1--------------------------------------
A lot of integer property questions can be solved using prime factorization.
For questions involving divisibility, divisors, factors and multiples, we can say:

If N is a factor by k, then k is "hiding" within the prime factorization of N

Consider these examples:
3 is a factor of 24, because 24 = (2)(2)(2)(3), and we can clearly see the 3 hiding in the prime factorization.
Likewise, 5 is a factor of 70 because 70 = (2)(5)(7)
And 8 is a factor of 112 because 112 = (2)(2)(2)(2)(7)
And 15 is a factor of 630 because 630 = (2)(3)(3)(5)(7)

---------------ASIDE #2--------------------------------------
IMPORTANT CONCEPT: The prime factorization of a perfect square will have an even number of each prime

For example: 400 is a perfect square.
400 = 2x2x2x2x5x5. Here, we have four 2's and two 5's
This should make sense, because the even number of primes allows us to split the primes into two EQUAL groups to demonstrate that the number is a square.
For example: 400 = 2x2x2x2x5x5 = (2x2x5)(2x2x5) = (2x2x5)²

Likewise, 576 is a perfect square.
576 = 2x2x2x2x2x2x3x3 = (2x2x2x3)(2x2x2x3) = (2x2x2x3)²
--------NOW ONTO THE QUESTION!------------------

Given: n² is divisible by 72 (in other words, there's a 72 hiding in the prime factorization of n²)
So, n² = (2)(2)(2)(3)(3)(?)(?)(?)(?)(?)... [the ?'s represent other possible primes in the prime factorization of n²]
Since we have an ODD number of 2's in the prime factorization, we can be certain that there is at least one more 2 in the prime factorization.
So, we know that n² = (2)(2)(2)(3)(3)(2)(?)(?)(?)(?)
So, while there MIGHT be tons of other values in the above prime factorization, we do know that there MUST BE at least four 2's and two 3's.
Now do some grouping to get: n² = [(2)(2)(3)(?)(?)...][(2)(2)(3)(?)(?)...]
From this we can see that n = (2)(2)(3)(?)(?)...

Question: What is the largest positive integer that must divide n?
(2)(2)(3) = 12.
So, the largest positive integer that must divide n is 12

Answer: B

Cheers,
Brent