1
$\begingroup$

At the moment I'm working on proving some statements and I've run into one that I can't seem to wrap my head around. It goes like this:

For $n \in \mathbb{Z}^+$, we define $\sqrt{n}$ as the real number $a$ such that $a^2 = n$. Show that if an integer $n > 1$ is composite, then it has a prime less than or equal to $\sqrt{n}$.

So far I've really only been able to prove by example using certain numbers but apart from that I'm rather lost on how I should approach and prove the statement. Any suggestions or help is much appreciated.

$\endgroup$
  • 1
    $\begingroup$ What can you infer about the size of integer that has at least two (prime) factors $> \sqrt{n}\,?\ \ $ $\endgroup$ – Bill Dubuque Jan 3 '15 at 19:46
  • $\begingroup$ You can try using Fundamental Theorem of Arithmetic by decomposing n into primes. Then you can argue it out by comparing the value of the primes when necessary. $\endgroup$ – Novice Jan 3 '15 at 19:58
4
$\begingroup$

The smallest divisor $p$ of $n$ greater than $1$ is not $n$ because $n$ is composite. But $p$ is a prime, because if $p$ has a non trivial divisor $d$, then $d$ is a divisor of $n$, which contradicts the minimality of $p$ as divisor of $n$.

Let $q=n/p$. Since $q$ is a divisor of $n$, we have that $p\le q$, that is, $$p\le\frac np$$ or $$p^2\le n$$

$\endgroup$
3
$\begingroup$

This results from two facts:

1) If $n$ is composite, the smallest divisor $a$ of $n$ is $\,\le \sqrt n$.

Indeed, if $ a>\sqrt n $, $ b=n/a $ divides $n$ and $\,b<\sqrt n$, so $a$ would not be the smallest divisor of $n$.

2) The smallest integer that divides $n$ is prime. Indeed, if it were not prime, it would not be the smallest.

$\endgroup$
1
$\begingroup$

Lets assume has at least 2 divisors,if 2 of those divisors,lets name them $p$ and $q$,are bigger than $\sqrt{n}$ than you have that $p\cdot q>\sqrt{n}\cdot\sqrt{n}=n$ hence at least one of $p,q$ is smaller than $\sqrt{n}$

$\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.