1
$\begingroup$

This turned out to be very obvious based on the definition of a prime number, so obvious I felt like not bothering, but I still want to see if there is a problem with the proof so far, seeings I am in general just terrible at proofs.

I observed that the greatest common divisor of the largest divisor of $n \cdot p_n$ and the largest divisor of $n\cdot\bigl\lfloor \frac{p_n}{n} \bigr\rfloor$ is always equal to $n$.

I then assumed this must be because $\bigl\lfloor \frac{p_n}{n} \bigr\rfloor$ and $p_n$ share no common divisor greater than 1, i.e they are coprime.

So the question became: Prove that $p_n$ and $\bigl\lfloor \frac{p_n}{n} \bigr\rfloor$ must be coprime.

And this is what have done so far:

since $\lnot (n | p_n)$ is true $\forall n \in \mathbb N$,

$\frac{p_n}{n}-\bigl\lfloor \frac{p_n}{n} \bigr\rfloor \ne 0\,\, \forall n \in \mathbb N$

and since we know :

$\gcd(k,p_n)=1$ $\forall k \leq p_n -1$

and

$\bigl\lfloor \frac{p_n}{n} \bigr\rfloor \lt p_n -1$ $\forall n \gt 1 \in \mathbb N$

we can substitute $k=\bigl\lfloor \frac{p_n}{n} \bigr\rfloor$

therefore

$\gcd(\bigl\lfloor \frac{p_n}{n} \bigr\rfloor,p_n)=1$

Hence showing that $\bigl\lfloor \frac{p_n}{n} \bigr\rfloor$ and $p_n$ are coprime.

$\endgroup$
  • 1
    $\begingroup$ We have to rule out $n=1$. In this case, $\lfloor\frac{p_n}{n}\rfloor$ is clearly smaller than $p_n$, hence must be coprime to $p_n$ $\endgroup$ – Peter Jun 10 '18 at 8:03
  • 1
    $\begingroup$ In addition to what Peter was saying, a prime number only has two divisors ($1$ and itself). This means a prime number is coprime to every number less than it. And since $\lfloor\frac{P_n}{n}\rfloor$ is obviously less than $p_n$ for $n>1$, they must be coprime. $\endgroup$ – Badr B Jun 10 '18 at 8:11
  • $\begingroup$ oh right yes I forgot to add $n \gt 1$. well I did say it was obvious. $\endgroup$ – Adam Jun 10 '18 at 8:24
  • $\begingroup$ but saying that a number is smaller than another therefore they are coprime makes no sense of course, so I'm really just eager to have my proofs checked easy or hard question, because ive found that I do mess up on very easy questions if I'm not careful $\endgroup$ – Adam Jun 10 '18 at 8:26
  • 1
    $\begingroup$ I see that, but the proof could've been a lot simpler. $\endgroup$ – Badr B Jun 10 '18 at 11:20

Your Answer

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

Browse other questions tagged or ask your own question.