Q: Prove that, if x and y are odd positive integers, then \$x^2 + y^2\$ is even but not divisible by 4.

We know that any odd positive integer is of the form \$2q + 1\$, where \$q\$ is an integer. So, let \$x = 2m + 1\$ and \$y = 2n + 1\$, for some integers m and n. we have \$x^2 + y^2\$\$x^2 + y^2 = (2m + 1)^2 + (2n + 1)^2\$\$x^2 + y^2 = 4m^2 + 1 + 4m + 4n^2 + 1 + 4n = 4m^2 + 4n^2 + 4m + 4n + 2\$\$x^2+ y^2 = 4(m^2 + n^2) + 4(m + n) + 2 = 4\{(m^2 + n^2) + (m + n)\}+ 2\$\$x^2 + y2 = 4q + 2\$, when \$q = (m^2 + n^2)+(m + n)\$\$x^2 + y^2\$ is even and leaves remainder 2 when divided by 4. \$x^2 + y^2\$ is even but not divisible by 4.

Q: Use Euclid's division lemma to show that cube of any positive integer is either of the form 9m, 9m + 1 or 9m + 8 for some integer 'm'.

Let \$a\$ and \$b\$ be two positive integers, and \$a > b\$\$a = (b \times q) + r\$ where \$q\$ and \$r\$ are positive integers and \$0 \le r< b\$Let \$b = 3\$ (If 9 is multiplied by 3 a perfect cube number is obtained) \$a = 3q + r\$ where \$0\le r < 3\$(i) if \$r= 0, a = 3q\$ (ii) if \$r = 1, a = 3q + \$1 (iii) if \$r = 2, a = 3q + 2\$Consider, cubes of theseCase (i) \$a = 3q\$\$a^3 = (3q)^3 = 27q^3 = 9(3q^3) = 9m\$ where \$m=3q^3\$ and '\$m\$' is an integer.Case (ii) \$a = 3q + 1\$\$a^3 = (3q + 1)^3\$ \$[(a + b)^3 = a^3+b^3 + 3a^2b+ 3ab^2]\$ \$=27q^3+ 1 + 27q^2 + 9q= 27q^3+ 27q^2+ 9q + 1\$ \$ = 9(3q^3+ 3q^2+ q) + 1 = 9m +1\$where \$m=3q^3 + 3q^2 + q\$ and '\$m\$' is an integer. Case (iii) \$a = 3q + 2\$ \$a^3= (3q + 2)^3= 27q^3+ 8 + 54q^2+ 36q\$\$= 27q^3- 54q^2+ 36q + 8 = 9 (3q^3+ 6q^2 + 4q) + 8\$ \$9m+8\$, where \$m=3q^3+6q^2+4q\$ and \$m\$ is an integer.\$\therefore\$ cube of any positive integer is either of the form \$9m, 9m+1\$ or \$9m+8\$ for some integer m.

Q: Prove that the product of three consecutive positive integers is divisible by 6.

Let the three consecutive positive integers be \$n\$, \$n+1\$ and \$n+2\$.Whenever a number is divided by \$3\$, the remainder obtained is either \$0,1\$ or \$2\$.Therefore, \$n=3p\$ or \$3p+1\$ or \$3p+2\$, where \$p\$ is some integer.If \$n=3p\$, then \$n\$ is divisible by \$3\$.If \$n=3p+1\$, then \$n+2=3p+1+2=3p+3=3(p+1)\$ is divisible by \$3\$.If \$n=3p+2\$, then \$n+1=3p+2+1=3p+3=3(p+1)\$ is divisible by \$3\$.So, we can say that one of the numbers among \$n, n+1\$ and \$n+2\$ is always divisible by \$3\$ that is:\$n(n+1)(n+2)\$ is divisible by \$3\$.Similarly, whenever a number is divided by \$2\$, the remainder obtained is either \$0\$ or \$1\$.Therefore, \$n=2q\$ or \$2q+1\$, where \$q\$ is some integer.If \$n=2q\$, then \$n\$ and \$n+2=2q+2=2(q+1)\$ is divisible by \$2\$.If \$n=2q+1\$, then \$n+1=2q+1+1=2q+2=2(q+1)\$ is divisible by \$2\$.So, we can say that one of the numbers among \$n\$, \$n+1\$ and \$n+2\$ is always divisible by \$2\$.Since, \$n(n+1)(n+2)\$ is divisible by \$2\$ and \$3\$.Hence, \$n(n+1)(n+2)\$ is divisible by \$6\$.

Q: If the \$HCF\$ of \$210\$ and \$55\$ is expressible in the form \$210 \times 5 + 55y,\$ find \$y.\$

Let us first find the \$HCF\$of \$210\$ and \$55\$.Applying Euclids division lemma on \$210\$ and \$55\$, we get\$210=55\times 3+45\$ Since the remainder \$45\neq0\$. So, we now apply division lemma on the divisor \$55\$ and the remainder \$45\$ to get\$55=45\times1+10\$ We consider the divisor \$45\$ and the remainder \$10\$ and apply division lemma to get\$45=4\times10+5\$ We consider the divisor \$10\$ and the remainder \$5\$ and apply division lemma to get \$10=5\times2+0\$ We observe that the remainder at this stage is zero. So, that last divisor i.e. \$5\$ is the \$HCF\$ of \$210\$ and \$55\$.\$\therefore\quad 5=210\times 5+55y\$\$\Rightarrow\quad 55y=5-210 \times 5=5-1050\$\$\Rightarrow\quad 55y=-1045\$\$\Rightarrow\quad y=\dfrac { -1045 }{ 55 } =-19\$

Q: Use Euclid's division lemma to show that the square of any positive integer is either of the form \$3m\$ or \$3m+1\$ for some integer m, but not of the form \$3m+2\$.

Let \$a\$ be the positive integer and \$b=3\$.We know \$a=bq+r\$, \$0 ≤ r < b\$Now, \$a=3q+r\$, \$0 ≤ r < 3\$The possibilities of remainder is \$0,1,\$ or \$2\$.Case 1 : When \$a=3q\$\$a^2 = (3q)^2=9q^2=3q\times 3q=3m\$ where \$m = 3q^2\$Case 2 : When \$a = 3q+1\$\$a^{ 2 }=(3q+1)^{ 2 }=(3q)^{ 2 }+(2×3q×1)+(1)^{ 2 }=3q(3q+2)+1=3m+1\$ where \$m= q(3q+2)\$Case 3: When \$a= 3q+2\$\$a^{ 2 }=(3q+2)^2=(3q)^{ 2 }+(2×3q×2)+(2)^{ 2 }=9q^{ 2 }+12q+4=9q^{ 2 }+12q+3+1=3(3q^{ 2 }+4q+1)+1=3m+1\$ where \$m= 3q^2+4q+1\$Hence, from all the above cases, it is clear that square of any positive integer is of the form \$3m\$ or \$3m+1\$.

Q: Find the largest four-digit number which when divided by 4, 7 and 13 leaves a remainder of 3 in each case.

Prime factors of \$4, 7\$ and \$13\$\$ 4 = 2 \times 2 \$\$7\$ and \$13\$ are prime numbers LCM \$( 4, 7 , 13)= 364\$we know that, the largest \$4\$ digit number is \$9999.\$Step 1 : divide \$9999\$ by \$364 ,\$ we get \$\dfrac {9999} {364} = 171\$ Step 2: subtract \$171\$ from \$9999\$ \$9999-171 = 9828\$Since a remainder of \$3\$ is to be left \$9282 +3 = 9831\$ therefore \$9831\$ is the number.

Q: Show that any positive odd integer is of the form \$6q + 1\$, or \$6q + 3\$, or \$6q + 5\$, where \$q\$ is some integer.

Using Euclid division algorithm, we know that \$a = bq + r,\$ \$0 \leq r \leq b\$ ----(1)Let \$a\$ be any positive integer and \$b = 6\$.Then, by Euclid’s algorithm, \$a = 6q + r\$ for some integer \$q\geq 0\$, and \$r = 0, 1, 2, 3, 4, 5\$ ,\$\:or\$ \$0 ≤ r < 6\$.Therefore, \$a = 6q \:or\: 6q + 1 \:or\: 6q + 2 \:or\: 6q + 3 \:or\: 6q + 4 \:or\: 6q + 5 \$\$6q+0: 6\$ is divisible by \$2\$, so it is an even number.\$6q+1: 6\$ is divisible by \$2\$, but \$1\$ is not divisible by \$2\$ so it is an odd number.\$6q+2: 6\$ is divisible by \$2\$, and \$2\$ is divisible by \$2\$ so it is an even number.\$6q+3: 6\$ is divisible by \$2\$, but \$3\$ is not divisible by \$2\$ so it is an odd number.\$6q+4: 6\$ is divisible by \$2\$, and \$4\$ is divisible by \$2\$ so it is an even number.\$6q+5: 6\$ is divisible by \$2\$, but \$5\$ is not divisible by \$2\$ so it is an odd number.And therefore, any odd integer can be expressed in the form \$6q + 1\:or\: 6q + 3\; or\: 6q + 5\$

Q: Show that every positive even integer is of the form \$2q\$ and every positive odd integer is of the form \$2q + 1\$, where q is a whole number.

(i) Let '\$a\$' be an even positive integer. Apply division algorithm with a and b, where \$b = 2\$ \$a = (2 \times q)+r\$ where \$0\le r < 2\$ \$a = 2q + r\$ where \$r = 0\$ or \$r = 1\$since '\$a\$' is an even positive integer, 2 divides '\$a\$'. \$\therefore r= 0\Rightarrow a= 2q+ 0 = 2q\$Hence, \$a = 2q\$ when '\$a\$' is an even positive integer. (ii) Let '\$a\$' be an odd positive integer. apply division algorithm with \$a\$ and \$b\$, where \$b = 2\$\$a = (2 \times q)+r\$ where \$0\le r < 2\$ \$a = 2q+ r\$ where \$r= 0\$ or 1 Here \$r \neq 0\$ (\$\because a\$ is not even) \$\Rightarrow r= 1\$\$\therefore a = 2q + 1\$Hence, \$a = 2q + 1\$ when '\$a\$' is an odd positive integer.

Q: \$144\$ cartons of coke cans and \$90\$ cartons of pepsi cans are to be stacked in a canteen. If each stack is of same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?

In order to arrange the cartons of the same drink in the same stack, we have to find the greatest number that divides \$144\$ and \$90\$ exactly. Using Euclid's division algorithm, to find the H.C.F. of \$144\$ and \$90\$.\$144=90\$ \$\times\$ \$1+54\$\$90 =54\$ \$\times\$ \$1 + 36\$\$54 =36\$ \$\times\$ \$1 +18\$\$36 =18\$ \$\times\$ \$2 + 0\$So, the H.C.F. of \$144\$ and \$90\$ is \$18\$.Number of cartons in each stack \$= 18.\$

Q: If the H.C.F of \$657\$ and \$963\$ is expressible in the form \$657 x -(963 \times 15)\$, find \$x\$.

Using Euclid's division\$a=bq+r\$\$963=657\times 1+306\$\$657=306\times 2+45\$\$306=45\times 6+36\$\$45=36\times 1+9\$\$36=9\times 4+0\$\$\therefore \$H.C.F\$=9\$\$\therefore 9=657x-(963\times 15)\$\$657x=14454\$\$x=22\$

Question 1

Prove that, if x and y are odd positive integers, then $x^2 + y^2$ is even but not divisible by 4.

Accepted Answer

We know that any odd positive integer is of the form $2q + 1$, where $q$ is an integer. So, let $x = 2m + 1$ and $y = 2n + 1$, for some integers m and n. we have $x^2 + y^2$$x^2 + y^2 = (2m + 1)^2 + (2n + 1)^2$$x^2 + y^2 = 4m^2 + 1 + 4m + 4n^2 + 1 + 4n = 4m^2 + 4n^2 + 4m + 4n + 2$$x^2+ y^2 = 4(m^2 + n^2) + 4(m + n) + 2 = 4\{(m^2 + n^2) + (m + n)\}+ 2$$x^2 + y2 = 4q + 2$, when $q = (m^2 + n^2)+(m + n)$$x^2 + y^2$ is even and leaves remainder 2 when divided by 4. $x^2 + y^2$ is even but not divisible by 4.

Question 2

Use Euclid's division lemma to show that cube of any positive integer is either of the form 9m, 9m + 1 or 9m + 8 for some integer 'm'.

Accepted Answer

Let $a$ and $b$ be two positive integers, and $a > b$$a = (b \times q) + r$ where $q$ and $r$ are positive integers and $0 \le r< b$Let $b = 3$ (If 9 is multiplied by 3 a perfect cube number is obtained) $a = 3q + r$ where $0\le r < 3$(i) if $r= 0, a = 3q$    (ii) if $r = 1, a = 3q + $1      (iii) if $r = 2, a = 3q + 2$Consider, cubes of theseCase (i) $a = 3q$$a^3 = (3q)^3 = 27q^3 = 9(3q^3) = 9m$           where $m=3q^3$ and   '$m$' is an integer.Case (ii) $a = 3q + 1$$a^3 = (3q + 1)^3$                $[(a + b)^3 = a^3+b^3 + 3a^2b+ 3ab^2]$      $=27q^3+ 1 + 27q^2 + 9q= 27q^3+ 27q^2+ 9q + 1$      $ = 9(3q^3+ 3q^2+ q) + 1 = 9m +1$where $m=3q^3 + 3q^2 + q$ and '$m$' is an integer. Case (iii) $a = 3q + 2$ $a^3= (3q + 2)^3= 27q^3+ 8 + 54q^2+ 36q$$= 27q^3- 54q^2+ 36q + 8 = 9 (3q^3+ 6q^2 + 4q) + 8$ $9m+8$, where $m=3q^3+6q^2+4q$ and $m$ is an integer.$\therefore$ cube of any positive integer is either of the form $9m, 9m+1$ or $9m+8$ for some integer m.

Question 3

Prove that the product of three consecutive positive integers is divisible by 6.

Accepted Answer

Let the three consecutive positive integers be $n$, $n+1$ and $n+2$.Whenever a number is divided by $3$, the remainder obtained is either $0,1$ or $2$.Therefore, $n=3p$ or $3p+1$ or $3p+2$, where $p$ is some integer.If $n=3p$, then $n$ is divisible by $3$.If $n=3p+1$, then $n+2=3p+1+2=3p+3=3(p+1)$ is divisible by $3$.If $n=3p+2$, then $n+1=3p+2+1=3p+3=3(p+1)$ is divisible by $3$.So, we can say that one of the numbers among $n, n+1$ and $n+2$ is always divisible by $3$ that is:$n(n+1)(n+2)$ is divisible by $3$.Similarly, whenever a number is divided by $2$, the remainder obtained is either $0$ or $1$.Therefore, $n=2q$ or $2q+1$, where $q$ is some integer.If $n=2q$, then $n$ and $n+2=2q+2=2(q+1)$ is divisible by $2$.If $n=2q+1$, then $n+1=2q+1+1=2q+2=2(q+1)$ is divisible by $2$.So, we can say that one of the numbers among $n$, $n+1$ and $n+2$ is always divisible by $2$.Since, $n(n+1)(n+2)$ is divisible by $2$ and $3$.Hence, $n(n+1)(n+2)$ is divisible by $6$.

Question 4

If the $HCF$ of $210$ and $55$ is expressible in the form $210 \times 5 + 55y,$ find $y.$

Accepted Answer

Let us first find the $HCF$of $210$ and $55$.Applying Euclids division lemma on $210$ and $55$, we get$210=55\times 3+45$  Since the remainder $45\neq0$. So, we now apply division lemma on the divisor $55$ and the remainder $45$ to get$55=45\times1+10$  We consider the divisor $45$ and the remainder $10$ and apply division lemma to get$45=4\times10+5$  We consider the divisor $10$ and the remainder $5$ and apply division lemma  to get $10=5\times2+0$ We observe that the remainder at this stage is zero. So, that last divisor i.e. $5$ is the $HCF$ of $210$ and $55$.$\therefore\quad 5=210\times 5+55y$$\Rightarrow\quad 55y=5-210 \times 5=5-1050$$\Rightarrow\quad 55y=-1045$$\Rightarrow\quad y=\dfrac { -1045 }{ 55 } =-19$

Question 5

Use Euclid's division lemma to show that the square of any positive integer is either of the form $3m$ or $3m+1$ for some integer m, but not of the form $3m+2$.

Accepted Answer

Let $a$ be the positive integer and $b=3$.We know $a=bq+r$, $0 &#8804; r < b$Now, $a=3q+r$, $0 &#8804; r < 3$The possibilities of remainder is $0,1,$ or $2$.Case 1 : When $a=3q$$a^2 = (3q)^2=9q^2=3q\times 3q=3m$ where $m = 3q^2$Case 2 : When $a = 3q+1$$a^{ 2 }=(3q+1)^{ 2 }=(3q)^{ 2 }+(2&#215;3q&#215;1)+(1)^{ 2 }=3q(3q+2)+1=3m+1$ where $m= q(3q+2)$Case 3: When $a= 3q+2$$a^{ 2 }=(3q+2)^2=(3q)^{ 2 }+(2&#215;3q&#215;2)+(2)^{ 2 }=9q^{ 2 }+12q+4=9q^{ 2 }+12q+3+1=3(3q^{ 2 }+4q+1)+1=3m+1$ where $m= 3q^2+4q+1$Hence, from all the above cases, it is clear that square of any positive integer is of the form $3m$ or $3m+1$.

Question 6

Find the largest four-digit number which when divided by 4, 7 and 13 leaves a remainder of 3 in each case.

Accepted Answer

Prime factors of $4, 7$ and $13$$ 4 = 2 \times 2 $$7$ and $13$ are prime numbers LCM  $( 4, 7 , 13)= 364$we know that, the largest $4$ digit number is $9999.$Step 1 : divide $9999$ by $364 ,$ we get $\dfrac {9999}  {364} = 171$ Step 2: subtract $171$ from $9999$ $9999-171 = 9828$Since a remainder of $3$ is to be left $9282 +3 = 9831$ therefore $9831$ is the number.

Question 7

Show that any positive odd integer is of the form $6q + 1$, or $6q + 3$, or $6q + 5$, where $q$ is some integer.

Accepted Answer

Using Euclid division algorithm, we know that $a = bq + r,$ $0 \leq r \leq b$ ----(1)Let $a$ be any positive integer and $b = 6$.Then, by Euclid&#8217;s algorithm, $a = 6q + r$ for some integer $q\geq 0$, and $r = 0, 1, 2, 3, 4, 5$ ,$\:or$ $0 &#8804; r < 6$.Therefore, $a = 6q \:or\: 6q + 1 \:or\: 6q + 2 \:or\: 6q + 3 \:or\: 6q + 4 \:or\: 6q + 5 $$6q+0: 6$ is divisible by $2$, so it is an even number.$6q+1: 6$ is divisible by $2$, but $1$ is not divisible by $2$ so it is an odd number.$6q+2: 6$ is divisible by $2$, and $2$ is divisible by $2$ so it is an even number.$6q+3: 6$ is divisible by $2$, but $3$ is not divisible by $2$ so it is an odd number.$6q+4: 6$ is divisible by $2$, and $4$ is divisible by $2$ so it is an even number.$6q+5: 6$ is divisible by $2$, but $5$ is not divisible by $2$ so it is an odd number.And therefore, any odd integer can be expressed in the form $6q + 1\:or\: 6q + 3\; or\: 6q + 5$

Question 8

Show that every positive even integer is of the form $2q$ and every positive odd integer is of the form $2q + 1$, where q is a whole number.

Accepted Answer

(i) Let '$a$' be an even positive integer. Apply division algorithm with a and b, where $b = 2$ $a = (2 \times q)+r$ where $0\le r < 2$ $a = 2q + r$ where $r = 0$ or $r = 1$since '$a$' is an even positive integer, 2 divides '$a$'. $\therefore r= 0\Rightarrow a= 2q+ 0 = 2q$Hence, $a = 2q$ when '$a$' is an even positive integer. (ii) Let '$a$' be an odd positive integer. apply division algorithm with $a$ and $b$, where $b = 2$$a = (2 \times q)+r$ where $0\le r < 2$ $a = 2q+ r$ where $r= 0$ or 1 Here $r \neq 0$ ($\because a$ is not even) $\Rightarrow r= 1$$\therefore a = 2q + 1$Hence, $a = 2q + 1$ when '$a$' is an odd positive integer.

Question 9

$144$ cartons of coke cans and $90$ cartons of pepsi cans are to be stacked in a canteen. If each stack is of same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?

Accepted Answer

In order to arrange the cartons of the same drink in the same stack, we have to find the greatest number that divides $144$ and $90$ exactly. Using Euclid's division algorithm, to find the H.C.F. of $144$ and $90$.$144=90$ $\times$ $1+54$$90 =54$ $\times$ $1 + 36$$54 =36$ $\times$ $1 +18$$36 =18$ $\times$ $2 + 0$So, the H.C.F. of $144$ and $90$ is $18$.Number of cartons in each stack $= 18.$

Question 10

If the H.C.F of $657$ and $963$ is expressible in the form $657 x -(963 \times 15)$, find $x$.

Accepted Answer

Using Euclid's division$a=bq+r$$963=657\times 1+306$$657=306\times 2+45$$306=45\times 6+36$$45=36\times 1+9$$36=9\times 4+0$$\therefore $H.C.F$=9$$\therefore 9=657x-(963\times 15)$$657x=14454$$x=22$

Euclids Division Algorithm

Language

Rate

REVISE WITH CONCEPTS

Euclid's Division Lemma

QUICK SUMMARY WITH STORIES

Euclid's division lemma

Prove that, if x and y are odd positive integers, then $x^{2} + y^{2}$ is even but not divisible by 4.

Use Euclid's division lemma to show that cube of any positive integer is either of the form 9m, 9m + 1 or 9m + 8 for some integer 'm'.

Prove that the product of three consecutive positive integers is divisible by 6.

If the $H C F$ of $210$ and $55$ is expressible in the form $210 \times 5 + 55 y,$ find $y .$

Use Euclid's division lemma to show that the square of any positive integer is either of the form $3 m$ or $3 m + 1$ for some integer m, but not of the form $3 m + 2$ .

Find the largest four-digit number which when divided by 4, 7 and 13 leaves a remainder of 3 in each case.

Show that any positive odd integer is of the form $6 q + 1$ , or $6 q + 3$ , or $6 q + 5$ , where $q$ is some integer.

Show that every positive even integer is of the form $2 q$ and every positive odd integer is of the form $2 q + 1$ , where q is a whole number.

$144$ cartons of coke cans and $90$ cartons of pepsi cans are to be stacked in a canteen. If each stack is of same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?

If the H.C.F of $657$ and $963$ is expressible in the form $657 x - (963 \times 15)$ , find $x$ .

Euclids Division Algorithm

Language

Rate

REVISE WITH CONCEPTS

Euclid's Division Lemma

QUICK SUMMARY WITH STORIES

Euclid's division lemma

Prove that, if x and y are odd positive integers, then x2+y2 is even but not divisible by 4.

Use Euclid's division lemma to show that cube of any positive integer is either of the form 9m, 9m + 1 or 9m + 8 for some integer 'm'.

Prove that the product of three consecutive positive integers is divisible by 6.

If the HCF of 210 and 55 is expressible in the form 210×5+55y, find y.

Use Euclid's division lemma to show that the square of any positive integer is either of the form 3m or 3m+1 for some integer m, but not of the form 3m+2.

Find the largest four-digit number which when divided by 4, 7 and 13 leaves a remainder of 3 in each case.

Show that any positive odd integer is of the form 6q+1, or 6q+3, or 6q+5, where q is some integer.

Show that every positive even integer is of the form 2q and every positive odd integer is of the form 2q+1, where q is a whole number.

144 cartons of coke cans and 90 cartons of pepsi cans are to be stacked in a canteen. If each stack is of same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?

If the H.C.F of 657 and 963 is expressible in the form 657x−(963×15), find x.

Prove that, if x and y are odd positive integers, then $x^{2} + y^{2}$ is even but not divisible by 4.

If the $H C F$ of $210$ and $55$ is expressible in the form $210 \times 5 + 55 y,$ find $y .$

Use Euclid's division lemma to show that the square of any positive integer is either of the form $3 m$ or $3 m + 1$ for some integer m, but not of the form $3 m + 2$ .

Show that any positive odd integer is of the form $6 q + 1$ , or $6 q + 3$ , or $6 q + 5$ , where $q$ is some integer.

Show that every positive even integer is of the form $2 q$ and every positive odd integer is of the form $2 q + 1$ , where q is a whole number.

$144$ cartons of coke cans and $90$ cartons of pepsi cans are to be stacked in a canteen. If each stack is of same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?

If the H.C.F of $657$ and $963$ is expressible in the form $657 x - (963 \times 15)$ , find $x$ .