Terence Tao Exercise 5.4.3: Integer part of $x$ proof.
Let $x=(x_1,x_2,\dots,x_n,\dots)$ be a Cauchy sequence of rational numbers, and let $\epsilon=\frac{1}{2}$. Then there exists an $M$ such that if $n,m\geq M$, $|x_n-x_m|<\epsilon$. That means, in particular, $x\in [x_M-\frac{1}{2},x_M+\frac{1}{2}]$.
Use the theorem for rational numbers, to show that there is an integer part $N_0$ of $x_M-\frac{1}{2}$, and that $N_0\leq x<N_0+2$. Then either $N_0\leq x<N_0+1$ or $N_0+1\leq x<N_0+2$.
If $x>0$ consider the set of natural numbers that are larger than $x$. It is non-empty by the Archimedean property, and it has a first element. Call that element $N+1$. We must have $N\leq x$ because otherwise $N+1$ wouldn't be the first element.
Your approach it leaving the chosen $N$ too lose because you are choosing it to be any $M<N+1$.