Good morning!


I have checked the following statement by random numbers of my choice. I am seriously looking for proof of the statement.


Statement: $m$ is said to be Fermat pseudo prime in base-3, when $m=ab$ with $a$ is some prime and $>3$ and $b$ is also prime and can be expressible in terms of $a$ (i.e., $b = 2a-1$).


Question(s): 1) can you prove the above statement?
 2) can we extend the same for other bases like 4, 5, 6 etc?


High regards,


Thanks in advance.


BIT.Ganmurt



Fermat pseudo prime base-3
I'm giving a solution to (1) in the form: If $m=ab$ where $a,b$ are primes exceeding 3 and $b=2a-1$, then $3^{m-1}\equiv1\pmod m$.


Note that it suffices to check that $3^{m-1}\equiv1\pmod a$ and $3^{m-1}\equiv1\pmod b$, by the Chinese remainder theorem.


Fermat's little theorem gives us $3^{a-1}\equiv1\pmod a$. But it's easy to check that $m-1=2a^a-a-1$ is a multiple of $a-1$. Therefore $3^{m-1}\equiv1\pmod a$.


Euler's criterion gives $3^{a-1} = 3^{(b-1)/2} \equiv (\frac 3b) \pmod b$, where $(\frac3b)$ is the Legendre symbol. But $a\not\equiv5\pmod6$, because if it were then $b=2a-1\equiv9\pmod{12}$, hence could not be prime. Therefore $a\equiv1\pmod6$, so that $b=2a-1\equiv1\pmod{12}$, and hence $(\frac3b) = (\frac b3) = 1$. Thus $3^{a-1}\equiv1\pmod b$, hence $3^{m-1}\equiv1\pmod b$ as before.


