While trying to find the first primitive root of modulo 109, I've ran across a very weird problem. Firstly I used Euler Criterion to try to find a number that would satisfy $a^{(p-1)/2}≡-1$ mod($p$). Hence $\phi(109)=108$, thus I was looking for $a^{54}≡1$ mod($109$). When checking $2$ for this relationship, it appears to satisfy it as $2^{54}≡108$ mod($109$). This was calculated using $mod$ function in Matlab. However, when I use Matlab and other online sources to find the first primitive root for my calculation they say it is $6$.
Where am I going wrong?
$2^{36}$ is already $1$ mod $109$. So it can't be a primitive root. Just because $2^{54}=-1$, that's not enough. You'd need $54$ to be the smallest power for which $2^n$ is $-1$. But this happens with $2^{18}$.