My C++ program behaves strange with wrong output?

Question

I want to view all solution for: X^12≡1(mod27) So I wrote the following C++ program which outputs only 1 even though 8 and 10 are possible values for x too.

Why is that?

#include <iostream>
#include <cmath>

int main() {
    for (int i = 0; i <= 2700000; ++i) {
        if (int(pow(i, 12))% 27 == 1) {
            std::cout << i << std::endl;
        }
    }
    std::cout << "Hello, World!" << std::endl;
    return 0;
}

Answer 1

The inbuild pow() function is not capable of handling so large number. Rather we have to use custom function to achieve that.

Here it is

#include <iostream>
#include <cmath>

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int main() {
    for (int i = 0; i <= 2700000; ++i) {
        if (binpow(i, 12, 27) == 1) {
            std::cout << i << std::endl;
        }
    }
    std::cout << "Hello, World!" << std::endl;
    return 0;
}

You can read more about that function from here: https://cp-algorithms.com/algebra/binary-exp.html

Answer 2

Oh, that's because you're using ints to calculate 12th powers, which are very large numbers. Int can only store numbers up to 2147483647, so use long long ints instead which can be much larger.

I rewrote your code and got this output: 1 8 10 17 19 26 28

#include <iostream>
#include <cmath>

int main()
{
    for (int i = 0; i <= 2700000; ++i)
    {
        long long int power = pow(i, 12);
        int mod = power % 27;
        if (mod == 1)
            std::cout << i << std::endl;
    }

    std::cin.get();
    return 0;
}