Сила модов или логическая проблема

Вот некоторый код, который я адаптировал, который касается функции Эйлера и функции Power Mod. каждый n, f2 всегда 3 вместо множества цифр. Кто-нибудь видит ошибку? phi(n) а также modpow(n) оба, кажется, работают нормально.

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}

int phi(int n)
{
int x = 0;
for (int i=1; i<=n; i++)
{
if (gcd(n, i) == 1)
x++;
}
return x;
}

int modpow(int base, int exp, int mod) // from stackoverflow
{
base %= mod;
long long result = 1;
while (exp > 0)
{
if (exp & 1)
result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}

int f2(int n) // f(f(n)) mod n
{
long long a = modpow(2, n, phi(n)) + 1;
return (modpow(2, a, n) + 1) % n;
}

// ...

int main()
{
int n = 520001;
while (true)
{
cout << "f2 " << f2(n) << endl;
if (f2(n) == 0)
{
// ...
}

n += 2;
}
return 0;
}

Значения f2(n) должно быть 9, 458278, 379578, ...