2
$\begingroup$

Assume $n \in N$ is composite. Prove if p is the least prime number dividing n, then $p^2 \leq n$

Approach: I tried to write the first few prime and composite numbers but I didn't any patter. Any hints to start this problem

$\endgroup$
  • $\begingroup$ Hint: if $p$ divides $n$ then $n=pm$. Now let $q$ be the least prime dividing $m$. $\endgroup$ – lulu Jun 3 '16 at 12:00
1
$\begingroup$

Hint: If $p$ is a prime number dividing $n$, then $n = kp$ for some integer $k$ (which is not 1 as $n$ is composite). What can you say about $k$ if $p^2 > n$?

$\endgroup$
  • $\begingroup$ Or rather, what can you say about the prime factors of $k$. Are they prime factors of $n$? Are they smaller than $p$? $\endgroup$ – Anamaki Jun 3 '16 at 12:13
  • $\begingroup$ by exahustion, I see that k is greater than p, but why does it make sense? $\endgroup$ – TheMathNoob Jun 3 '16 at 12:16
  • $\begingroup$ How do you get that? I don't understand $\endgroup$ – Anamaki Jun 3 '16 at 12:18
  • $\begingroup$ 10=5*2, so 2 is the least prime number and 5 is k $\endgroup$ – TheMathNoob Jun 3 '16 at 12:19
  • $\begingroup$ But we also assumed $p^2 > n$, remember. $\endgroup$ – Anamaki Jun 3 '16 at 12:21
1
$\begingroup$

Let $p$ be the least prime dividing $n$. Since n is a composite, $ \exists q \neq 1$ prime, such that $ q | \frac{n}{p} $. By assumption $ p \leq q $

$pq \leq n$ as $p$ and $q$ both divide $n$.

$ \implies pp \leq pq \leq n $

$ p^2 \leq n $

$\endgroup$
0
$\begingroup$

By the Fundamental Theorem of Arithmetic, you can write $$ n=\prod_{j=1}^hp_j^{\alpha_j} $$ where $p_1< p_2<\ldots< p_h$ and $\alpha_j$ are positive integers. By assumption, we have $p=p_1$. Moreover, because $n$ is composite, we know that either $h>1$ or $\alpha_1>1$. In the former case, $n\geq p_1^{\alpha_1}p_2^{\alpha_2}\geq p_1p_2>p_1^2=p^2$; in the latter case, $n\geq p_1^2=p^2$.

$\endgroup$

Your Answer

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

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