MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question

closed as off-topic by Will Jagy, Daniel Moskovich, Jack Huizenga, Andrey Rekalo, Emil Jeřábek Jan 28 '14 at 12:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Will Jagy, Jack Huizenga, Andrey Rekalo, Emil Jeřábek
If this question can be reworded to fit the rules in the help center, please edit the question.

I don't understand the question: What do you mean by "expressible in terms of $a$", and what is the statement you would like to prove about these numbers? – Daniel Moskovich Jan 28 '14 at 6:30
Daniel Moskovich! Thank you for your comment. Prove that $3^{m-1}$ $= 1(mod m)$, if $m = ab$ and $a$ is prime number $>3$ and $b = 2a-1.$ – BIT.Ganmurt Jan 28 '14 at 6:56
up vote 1 down vote accepted

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.

share|cite|improve this answer
@explain about how you got a is not congruent to 5 mod 6? – BIT.Ganmurt Jan 28 '14 at 10:49
If $a\equiv5\pmod6$ then $b=2a-1$ is a multiple of $3$. That's impossible since $b$ is prime. – Greg Martin Jan 28 '14 at 18:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.