If you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).
Well, if you "bring overflow into the mix", what you get depends on your behavior when overflowing.
If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to
2ᵃ * 3ᵇ ≡ n (mod 2⁶⁴)
If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we want
3ᵇ ≡ n (mod 2⁶⁴)
for odd n.
If I'm reading wikipedia correctly, we know that this will fail for some n:
> In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n).
This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus).
The article continues:
> a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0.
2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.
If you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).
Well, if you "bring overflow into the mix", what you get depends on your behavior when overflowing.
If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to
If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we want for odd n.If I'm reading wikipedia correctly, we know that this will fail for some n:
https://en.wikipedia.org/wiki/Primitive_root_modulo_n
> In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n).
This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus).
The article continues:
> a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0.
2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.