[thaumasiotes]

If you're allowed to multiply as many 32-bit numbers as you want, the only numbers you won't be able to achieve by so doing are those with any prime factor larger than 2^32.

This is more than just the prime numbers. For example, a 41-bit prime can be multiplied by 16 and it will still fit into 64 bits.

[nyeah]

What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.

[shiandow]

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).

[thaumasiotes]

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:

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⁶⁴.

[shiandow]

Interesting, one of those situations where the odd primes behave slightly differently. Which means it's probably above my paygrade.

I did say things would get complicated.