Consider the following proof question: prove for all natural numbers $n$, if $n\mid a$ and $n\mid b$ then $n\mid\gcd(a,b).$
Using the prime factorization of $a, b$ and $\gcd(a,b),$ this proof should be straightforward. Namely, since $n\mid a$ and $n\mid b$, then the prime factorization of $n$ must contain the same primes in $\gcd(a,b),$ since the prime factorization of $\gcd(a,b)$ will contain the minimal number of primes from both $a$ and $b$.
That said, is there a way to do this proof with induction? If so, what would the induction hypothesis ($P(k)$) be and how could I use that to prove the following case ($P(k+1)$) after the inductive hypothesis?
I guess doing an induction proof for this is really senseless. As from the questions I have tried, induction is very useful when it comes to proving properties or theorems for a continuum of numbers (as in the case of proving the FTA - Fundamental Theorem of Arithmetic). Here we aren't considering any continuum - we take two numbers such that they divide a particular number and show that their GCD can also divide the same number. Coming to the FTA, we need to prove that all of the integers are either primes or a product of various powers of various primes, and while doing so we generalize it over a continuum of numbers, thus making the statement hold for all integers. The problem in question is also a generalized property, but we take two arbitrary numbers instead of a whole sequence of them. If you ever try extending this over any number of integers as well, using induction is meaningless as still it's obvious that there always exists a GCD for an arbitrarily taken set of integers and that since all those numbers are expressible as a multiple of this GCD and since they divide the number taken, the GCD also divides the number by Euclid's lemma on divisibility.
A better proof (possibly; I am still a bit weak at proof writing) would be:
Hypothesis: we need to prove, $(a \mid n) \land(b \mid n) \implies \gcd(a,b) \mid n$
If you're going to use the prime factorisation of both the numbers: Let $a = \prod\limits_{i=1}^{k}p_i^{m_i}$ and $b = \prod\limits_{i=1}^{l}q_i^{n_i}$ where $p_i,q_i$ are primes and $m_i,n_i$ are respective powers of the $i$th prime if you ever consider their order, but for now let's just generalize it.
The GCD of $a$ and $b$ will have all the primes common to both $a$ and $b$ since it will divide both $a$ and $b$.
Notice that since $a \mid n$, by FTA we can say that $ p_i \mid n \space \forall \space p_i \mid a$. The same can be done for $b$ as well.
Since the GCD will have all primes that are common to both $a$ and $b$, we can, WLOG, assume that $ \gcd(a,b) = c_1^{r_1}c_2^{r_2}\dots$ where $c_v^{r_v}$ are the common primes raised to their respective common powers. We see that all of the primes of $a$ or $b$ can divide $n$ and these primes are present in the GCD as well, but their powers are $\min(v_{c_V}(a),v_{c_V}(b))$ and is less that $v_{c_v}(n)$ since both $a$ and $b$ can divide $n$. And hence we see that all the primes in the GCD are also present in $n$ and thus we see, $\gcd(a,b) \mid n$ (I guess I have made some loopholes in this proof, so please point them out, if any.)
An even easier thing would be to deduce that $a \mid n \implies n = ax$ and $b \mid n \implies n = by$ and since $(\gcd(a,b) \mid a)\land(\gcd(a,b) \mid b)$, $\gcd(a,b) \mid ax$ and $\gcd(a,b)\mid by$ and thus we see $\gcd(a,b) \mid n$. This is, obviously, a rephrasing of the above proof, without having to specifically consider all primes.