Proof by induction of Bézout's identity for $n$ integers with no common factors Question:
Let $n\geq 2$. For any integers $a_1,a_2,\ldots,a_n$ having no common factor, there exists integers $x_1,x_2,\ldots,x_n$ such that 
$$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = 1.$$
This is what they did and I don't understand $(\star)$ and $(\star \star)$:
$P(n)$ is the predicate above.
Basis:
$P(2)$ is true by Bezout's Identity.
Induction step:
Let $k\in\mathbb{N}$ with $k\geq 2.$
Now assume that $P(k)$ is true, and let $a_1,a_2,\ldots,a_k,a_{k+1}$ be integers with no common factor.
We must deduce that
$$a_1 x_1 + \ldots + a_k x_k + a_{k+1}x_{k+1} = 1$$
for some integers $x_1,x_2,\ldots,x_{k+1}$.
Let $g$ be the greatest common divisor of $a_1,\ldots,a_k$ $\qquad(\star)$
Then $\frac{a_1}{g},\ldots,\frac{a_k}{g}$ have no common factor.
By the induction assumption, there exists integers $y_1,\ldots,y_k$ such that
$$\left(\frac{a_1}{g}\right)y_1 + \ldots + \left(\frac{a_k}{g}\right)y_k = 1.$$   
Also, $g$ and $a_{k+1}$ cannot have a common factor (else, $g$ would be a common factor of $a_1,\ldots,a_{k+1}$.)  
So by the Basis case, $\qquad (\star\star)$
$$gz+a_{k+1}z_{k+1} = 1$$
for some integers $z,z_{k+1}$.  
So my query is:
$(\star)$: I thought that from assumption in the induction case, we assumed all those integers have no common factor?
$(\star\star)$: Why do we use the basis case? Is this allowed? I've never seen a proof by induction in the induction step that uses the "basis case"?
 A: $1.$ $g = 1$ in this case. No common factor, hence $gcd = 1$ for the numbers $\quad$   $2.$ There is no problem in using the basis case as you know that it is true(in this case Bezout's identity), a conclusion drawn from it can not be false. Also, you should know that Bézout's identity can be extended to more than two integers: if
$gcd(a_{1},a_{2},\ldots ,a_{n})=d$ 
then there are integers $x_{1},x_{2},\ldots ,x_{n}$ such that
$d=a_{1}x_{1}+a_{2}x_{2}+... +a_{n}x_{n}$  where $d$ is the $gcd$
A: (*) What the question is asking you to prove is that you can do this for any set of numbers which have no factor common to all of them except $1$.
Now the problem is that when you take $k+1$ numbers with this property, and then look at the first $k$, they may not have the required property. So in order to use your induction hypothesis you need to convert the first $k$ numbers to a set with no common factor (other than $1$). You can do this by dividing by the HCF.
For example, going from $k=2$ to $3$. You might be given three numbers $6,10,15$. These have no common factor, but any two of them do have a common factor. Here you have $g=2$, $2\times 3-1\times 5=1$, and so $2\times 6-1\times 10=2$. Now you use $8\times 2-1\times 15=1$ to get $8\times (2\times 6-1\times 10)-1\times 15=1$, i.e. $16\times 6-8\times 10-1\times 15=1$.
(**) Yes, it's quite common in induction proofs that you use more than just the previous value of $k$ - by this point you know it's true for all previous values of $k$, so that's fine. This is sometimes called "strong induction".
