0

I have just started revising number theory and I am getting stuck on a lot of the "prove that" questions. Any tips and advice would be much appreciated!

Geoff
  • 461

3 Answers3

1

Suppose $n$ is not prime. Then the decomposition of $n$ is $$ n = 2^{\alpha_2} 3^{\alpha_3} 5^{\alpha_5} \cdots$$

Take the least $i$ such that $\alpha_i \geqslant 1$ ($i$ is a prime). Then $n = i\times q$, where $q$ is a positive integer, greater than $i$ because $n$ is not prime.

Suppose $i > \sqrt n$. Then $q > \sqrt n$, and thus $i\times q = n > n$. Contradiction.

Kevin Quirin
  • 1,395
1

one method of proving a statement is to negate it and derive a contradiction. so, suppose $n \gt 1$ is a compound integer not divisible by any prime $\le \sqrt{n}$.

then $n$ is divisible by at least two primes, say $p$ and $q$ and each is $\gt \sqrt{n}$

so $n \ge pq \gt \sqrt{n} \sqrt{n}=n$

but a number cannot be strictly larger than itself, which is the required contradiction

David Holden
  • 18,040
1

Hint: $n \geq 1$ composite, then write $n=a\cdot b$, with $1< a,b <n$. By contradiction, suppose that niether $a$ nor $b$ is less than $\sqrt{n}$, then $\dots $

Now, if both $a$ and $b$ are not prime, you can easily extract a prime satisfying the above property.

Nizar
  • 2,782