To dive straight into the question: is there a form of induction which works on prime numbers? I've thought, and while I'm pretty sure it can be done om numbers such as even numbers or numbers divisible by something, since they are equally distributed, the primes follow no specific formula, hence my question.
More generally, if we have a property which works only on specific sets of numbers (such as, for example, the squarefree numbers), can we prove it true using induction or any variant thereof?
Induction works in any well-ordered set such as $\,\Bbb N.\,$ Since nonempty subsets of well-ordered sets inherit the well-ordering, induction also works on such subsets.
For example, any nonempty set of primes contains a least prime. This is often used in number theory, e.g. below to prove that no odd $\,n>1\,$ divides $\,2^n-1,\,$ from here.
Hint $ $ Key Idea $ $ if $\ a\not\equiv 1,\,\ a^n\equiv 1\,$ then the order of $\,a\,$ divides $\,n\,$ so is $\ge$ least prime $\,p\mid n.$
Thus, $ $ mod $\rm\color{#c00}{least}$ prime $\,p\mid n\!:\ 2^n \equiv 1\Rightarrow\, 2\,$ has order $\,k\mid n\,\color{#c00}{\Rightarrow}\ k \ge$ $\,p\,\Rightarrow\, 2^{p-1}\not\equiv 1\,\Rightarrow\!\Leftarrow$