Show that $q'$ is the quotient of euclidean division of the number $n$ by $ab$

Question

Let $n\in N$ and $a,b\in N$:

1- $q$ the quotient of euclidean division of $n$ by $a$

2- $q'$ the quotient of euclidean division of $q$ by $b$

Show that $q'$ is the quotient of euclidean division of $n$ by $ab$

I thought about unicity of $(q,r)\in N$ in $a=qb+r$.

We have

$n=qa+r_1$ with $0\le r_1<a$

$q=q'b+r_2$ with $0\le r_2<b$

We have to show that $n=q'(ab)+r_3$ where $0\le r_3<ab$

What I tried is puting $n=q'ab+ar_2+r_1$ and show that $0\le ar_2+r_1<ab$

But I'm blocked because I obtain $0<ar_2+r_1<a(b+1)$

Answer 1

The hypotheses mean that

1. $n=aq+r$, with $0\le r<a$
2. $q=bq'+r'$, with $0\le r'<b$

Therefore $$ n=aq+r=a(bq'+r')+r=(ab)q'+(ar'+r) $$ and you want to show that $0\le ar'+r<ab$.

Until now your argument is sound.

Clearly $ar'+r\ge0$. Suppose $ar'+r\ge ab$; then $r\ge a(b-r')$, in particular $$ a(b-r')<a $$ that means $b-r'<1$. Since $b-r'>0$, this is a contradiction.