idea
A system based only on primes: Skolem arithmetic
This is the theory of whole numbers with multiplication only, no addition. Every number is a unique bundle of primes (12 = 2·2·3), so multiplication means “combine the bundles”. In that world you can talk about primes, divisibility and “infinitely many primes” with no trouble.
It is complete: every statement it can express is provable or disprovable, and a computer can even decide which. Gödel does not touch it. Addition alone (Presburger arithmetic) is also complete.