Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

how can we find the greatest integer which is a perfect square and which divides an integer? I believe factorisation can be used here but am not sure how to get the result out of it for all prime, non-prime, and also integers which are themselves perfect square(e.g 1296) ? Thanks.

share|improve this question
1  
If $n = \prod_i p_i^{\alpha_i}$ then $k = \prod_i p_i^{f(\alpha_i)}$ where $f(x)$ is the greatest even number smaller than $x$, i.e. $f(x) = 2\left\lfloor\frac{x}{2}\right\rfloor$. –  dtldarek Mar 30 '12 at 9:30
    
oeis.org/A008833 –  Charles Apr 4 '12 at 15:03

1 Answer 1

up vote 6 down vote accepted

Say that you are given the integer $n$ and want to find the largest perfect square $k$ such that $k \mid n$.

First, find the prime factorization of $n$: $$n = p_1^{e_1} \cdots p_m^{e_m}$$ Let $$k = p_{1}^{e_1'} \cdots p_{m}^{e_m'}$$ where $e_m'$ is the largest even integer smaller than or equal to $e_m$, which will make $k$ the largest perfect square which divides $n$.

For example $$1296 = 2^4 \cdot 3^4$$ and both exponents are even, so you get the same number.

Since $$1 609 699 = 7^3 \cdot 13 \cdot 19^2$$ the largest perfect square which divides this is $7^2 \cdot 19^2 = 17689$.

And $$3458 = 2 \cdot 7 \cdot 13 \cdot 19$$ has no exponents larger than one, so the largest perfect squares which divides it is 1.

share|improve this answer
    
thanks a lot Calle :) –  pranay Mar 30 '12 at 10:29
    
You are welcome. :) –  Calle Mar 30 '12 at 13:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.