Prove that $p$ is Composite by Showing that It is Not a Pseudoprime Basis $2$

Question

I have the following problem: Prove that $m \notin \mathbb{P} $ by showing that m is not a pseudoprime to the basis $2$.
I think normally the problem is not that difficult, but in this case $m= 3363148097 $, which makes it very difficult to find its prime factorization and other properties that could help solve the problem. Also trying to actually calculate the modulo by breaking the power $^{m-1}$ is complicated. I think I might be missing something about the fact that the base is 2, maybe there are some more properties for that...

Answer 1

Hint: Dividing out factors of $2$ from $m-1$ shows that $$m-1=336148096=2^7\times2626157,$$ which allows you to factor $2^{m-1}-1$ as follows: $$2^{m-1}-1=2^{2^7\times2626157}-1=(2^{2626157}-1)\prod_{k=0}^6(2^{2^k\times2626157}+1).$$

Answer 2

You want to compute $2^{m-1}\bmod m$. Note that you can find $2^{2k}\bmod m$ from $2^k\bmod m$ by a single multiplication modulo $m$, and $2^{2k+1}\bmod m$ from $2^k\bmod m$ by a single addition modulo $m$. Thus to compute $2^{m-1}\bmod m$ amounts to less than thirty multiplications modulo $m$ and a handful additions modulo $m$.

Answer 3

Let $m = 3363148097$. Now, if $m$ is prime, then $m | 2^{m-1}$.

If $m$ is a pseudoprime, then $m | 2^{m-1}$.

Hence, if $m \nmid 2^{m-1}$, then $m$ must be composite.