0

A Claim:

Let $A$ be a set contains all $n\geq3$ Such that $n$ is divisible by all the numbers less or equal to $n$. $$A=\{n\geq3 \mid m\mid n, \forall m\le n \}$$

Show that $A=\emptyset$.

This is just another way to explain the question in the title, and why $n\geq3$? It’s because $1,2$ are divisible by all numbers less than themselves.

I don’t have any idea how to prove this claim, i’ve just tried a lot of values and it seems valid, maybe the best way to prove it it’s by contradiction.

PNT
  • 4,164

2 Answers2

3

Suppose that $A\ne \emptyset$, then exists $n\in A$.

Since every $m\leq n$ divides $n$ then also $n-1\mid n$. But then $$n-1\mid n-(n-1) =1$$ so $n-1 =1$ a contradiction, since $n\geq 3$. Thus $A= \emptyset$.

nonuser
  • 90,026
  • I didn’t think about $n-1$, good answer. – PNT Feb 22 '21 at 21:09
  • @Yassir How to discover the proof: it suffices to find some $m$ coprime to $n$ with $, 1 < m < n.,$ Always $1$ is coprime to $n$ but we need something bigger. But coprimes come in "reflection" pairs $,m\leftrightarrow n-m,$ since $,\gcd(m,n) = \gcd(n-m,n),$ by Euclid. Thus we can use this reflection of $1$, i.e. $,n-1.,$ Arithmetically this reflection is just negation $!\bmod n,,$ since $,n-m\equiv -m\pmod{!n},,$ and it is clear that negation of $,m,$ doesn't alter its gcd with $,n.,$ That's the key idea. – Bill Dubuque Feb 23 '21 at 08:53
1

$n-1$ does not divide $n$ for any $n>2$, because $\frac{n}{n-1}$ gives a value between 1 and 2.

RobertTheTutor
  • 7,415
  • 2
  • 10
  • 34