Claim : if $\forall j \in [k]$, $q_j$ does not divides $n$, $\text{GCD}(n,p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} q_1^{\beta_1} q_2^{\beta_2} \cdots q_k^{\beta_k}) = \text{GCD}(n,p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} )$

My attempt : Let us assume that $\text{GCD}(n,p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} )$ contains some $q_i^{\beta_i}$ that means $q_i^{\beta_i}$ divides $n$ which is a contradiction .

  • 1
    $\begingroup$ So, what is your question exactly? $\endgroup$ Feb 10 '18 at 12:12
  • 1
    $\begingroup$ Is my proof correct or give better way to prove the above claim $\endgroup$
    – user437890
    Feb 10 '18 at 12:12

Let $a=\gcd(n,p_{1}^{\alpha_{1}},\cdots ,p_{k}^{\alpha_{k}},q_{1}^{\beta_{1}},\cdots ,q_{k}^{\beta_{k}})$ and $b=\gcd(n,p_{1}^{\alpha_{1}},\cdots ,p_{k}^{\alpha_{k}})$.

Then, $a|n$ and $a|p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$, so in particular, $a|n$ and $a|p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}} q_{1}^{\beta_{1}}\cdots q_{k}^{\beta_{k}}$. Then, by definition of $\gcd$, $$a|b.$$

Now, let us show that $\gcd(b,q_{i}^{\beta_{i}})=1$. If not, since $q_{i}$ is prime, the unique divisors of $q_{i}^{\beta_{i}}$ are $q_{i}^k$ or $-q_{i}^k$ for $k\in \{1,\cdots, \beta_{i}\}$. Then, the $\gcd$ would be one of them, so $q_{i}$ would divide $n$, which is a contradiction. Therefore, we have that $$b| p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}q_{1}^{\beta_{1}}\cdots q_{k}^{\beta_{k}},$$ and then, since $\gcd(b,q_{i}^{\beta_{i}})=1$, $$b|p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}.$$ So by the same argument as above, $b|a$.

Finally, $\gcd$ are assumed to be positive and $a|b$ and $b|a$, so $a=b$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy