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$
  • 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 '17 at 21:07
  • 5
    $\begingroup$ I think all you need is that if $a\mid b$ and $b\mid c$ then $a\mid c$ . $\endgroup$ – amd Jan 1 '17 at 21:07
47
$\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
    $\begingroup$ Ooh, that makes a lot of sense. Proof by contradiction was the way to go for this. $\endgroup$ – Eli Sadoff Jan 1 '17 at 21:09
15
$\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$

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.