Polynomial reduction from unbounded knapsack problem to general integer programming

Question

Given an oracle that can solve in polynomial time:

$$a^Tx=b$$ $$x \geq 0$$

So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)

With this oracle how can this be solved in polynomial time: $$Ax=b$$ $$x \geq 0$$

where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.

My thoughts:

Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.

Answer 1

Hint: What do you know about the complexity class of the unbounded knapsack problem? Is it in P? Is it NP-hard?

Now what do you know about the complexity class of LP? Is it in NP?

Think a bit about your answers to those two questions and see if that helps you see one path forward. (There's a short proof of your desired result that doesn't require much detailed mathematics.)

---

Once you've figured that out: if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...)

---

Once you've worked out that: you should now know there is a reduction. So look at the proofs of each of the steps of reasoning I walked you through. Review these proofs. Those proofs will construct a reduction for you. So, work out what reduction is implicit in the proofs. You should be able to take it from here!