18
$\begingroup$

I am working on some things related to arithmetic derivatives, and I was writing a program to calculate the arithmetic derivative. In working on my program I came across an assumption that I have made, but I could not prove that it was true and it was quite frustrating to me.

My hypothesis is for any $n \in \mathbb{N}$, the smallest number, $a \in \mathbb{N}/\{1\}$ such that $a \vert n$ should be prime. My beginning of a proof for this was this

Using the fundamental theorem of arithmetic, for all $n \in \mathbb{N}/\{1\}$, that either $n$ is prime, or that $n$ has a unique prime factorization. If $n$ is prime, the proof is trivial, as the prime factorization for all $p \in \mathbb{P}$ is just $p$; however, for the case of $n$ being composite, the proof became quite difficult for me.

For the case of a number $c$ such that $c \in \mathbb{N}/\{1\}$ and $c \notin \mathbb{P}$, we can say that there exists at least two numbers, $a$ and $b$ such that fulfill the following four statement

  1. $1 < a \le b < c$
  2. $a \vert c$
  3. $b \vert c$
  4. $ab = c$

My thought process thereby went into dividing $c$ into odds and evens. We can say that this theorem is true for all even numbers, $e$, rather trivially as well because for all $e \in \{2k:\mathbb{N}/\{1\}\}$ that $2\vert e$ and $2$ is also the smallest integer that could possibly fulfill the above criteria thereby making $a = 2$ and fulfilling the theorem for all even numbers.

The part that I cannot figure out however is odd numbers. My intuition is telling me this must be true, but I cannot figure out a proof of this theorem for odds and I was wondering if

  1. Is this theorem actually true?
  2. If so, how can this be proven for odds?
$\endgroup$
2
  • 4
    $\begingroup$ Let $d$ be the smallest divisor. If $d$ were composite, then $d=rs$ with $1<r,s<d$ and both $r,s$ are also divisors. $\endgroup$
    – lulu
    Jan 1, 2017 at 21:07
  • 6
    $\begingroup$ I think all you need is that if $a\mid b$ and $b\mid c$ then $a\mid c$ . $\endgroup$
    – amd
    Jan 1, 2017 at 21:07

4 Answers 4

51
$\begingroup$

Let $n\in\Bbb N$ and let $a\in\Bbb N\setminus\{1\}$ be the smallest divisor of $n$. If $a$ is prime, you're done. If not, then $a$ is composite, and so can be written $a = bc$ for $b,c\in\Bbb N\setminus\{1\}$. But then $b,c < a$, and $b\mid n$, contradicting the assumption that $a$ was the smallest divisor.

$\endgroup$
1
  • 1
    $\begingroup$ Ooh, that makes a lot of sense. Proof by contradiction was the way to go for this. $\endgroup$
    – Eli Sadoff
    Jan 1, 2017 at 21:09
16
$\begingroup$

No contradiction: just use the definition of prime number.

Consider the set $D=\{a\in\mathbb{N}:a\mid n, a>1\}$. The set is non empty, because $n\in D$ (assuming $n>1$, of course).

Let $p=\min D$. If $x\mid p$, then $x\mid n$ and $x\le p$. If also $x>1$, then $x\in D$. By minimality of $p$, we conclude $x=p$. Therefore $p$ is prime.

$\endgroup$
3
$\begingroup$

One can also avoid a proof by contradiction. By the fundamental theorem of arithmetic, every divisor $d > 1$ of $n$ is a product of some primes dividing $n$.

Let $p$ the smallest prime divisor of $n$. By the above, all divisors $d > 1$ of $n$ are greater than or equal to $p$, as every such $d$ is a product of factors all greater than or equal to $p$.

$\endgroup$
2
$\begingroup$

If you just want to prove that the smallest non 1 divisor of a number is always prime, all you have to do is proceed by contradiction.

Let N be a composite number ( even or odd doesn't matter ). Let's assume that N's smallest non 1 divisor is not a prime, let's call this composite divisor c. If c is composite then using the fundamental theorem of arithmetic, c can be expressed as the factorisation of prime numbers all < to c. Let p be one of c's factors. Then since c | N and p | c then p | N , but p < c ( since p is a factor of c ), which contradicts the assumption that the smallest divisor of N is c.

I don't know if this is what you wanted and if I have been clear enough.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .