Only method is to put your problem in some class of perfectly solvable problems, and show its insolubility inside a class.
Example is application of Galois theory to prove, that equation's $x^5 + x + 1 = 0$ solution is not expressible in terms of radicals.
Other example is expressing informal notion of algorithm as a Turing machine and next prove undecidability of halting problem for any Turing machine.
Given these two results, do we have sufficient evidence to think that those two problems (analytical roots of given polynom and halting problem) are really insoluble?
May be we must regard this as evidence, that idea to solve polynomial equations in radicals needs to be replaced, and that Turing machine is too narrow abstraction?
Since we still don't know anything better, than solving equations in radicals, and we don't know any exceptions for Church–Turing thesis. That is why we are using words like "insolubility in radicals", "undecidable [if Church-Turing thesis holds] problem", etc.
If you want to do so in number theory for prime numbers, you must first create a framework for similar tasks, rich enough to comply with intuitive notions, and then show, that exact problem like "next prime number for given one" have no solution inside this framework. Or may be you will see, that it really have one...