# Showing $x(2x - 1)$ is a Fermat pseudoprime given $x$ is odd prime and other conditions

I am still stuck on this problem.

Given $x$ and $y = 2x - 1$ are both odd primes, then prove that $m = x y$ is a pseudoprime to the base $b$ if and only if $(b/y) = 1$ (Legendre symbol), and $x$ does not divide $b$.

Here is what I have so far:

Assume $m$ is pseudoprime to base $b$ so I have:

$b^{m-1}=1$ (mod m)

Now $m = x(2x - 1)$ so $m - 1 = 2x^2 - x - 1 = (2x + 1)(x - 1)$

Since $x$ divides $m$, then I can write

$b^{m - 1} = 1 \pmod x$

Using Fermat's little theorem, and $m - 1 = (2x + 1)(x - 1)$ I get:

$b^{2x + 1} = 1 \pmod x$

I am not sure where to go from here, am I even on the right track for showing the first direction?

• PS, how can I get an expression like b^(2x+1) to be properly displayed? If I use $$then I only get the first symbol after the base as an exponent., Thanks. – user286813 Nov 19 '15 at 22:31 • Put the exponent in { } e.g. b^{2x+1}. Use { }, not ( ) – Mirko Nov 19 '15 at 22:48 ## 1 Answer Hint : Use Euler's theorem : If p is a prime and p does not divide a, we have$$\large a^{\frac{p-1}{2}}\equiv\ (\frac{a}{p})\ \ \ (\ mod\ p\ )$$We have$$b^{x-1}\equiv (\frac{b}{2x-1})\ mod\ (\ 2x-1\ )

Take it from here.

• Could you please complete one direction of the proof? I am still not sure hwo to do it – user286813 Nov 20 '15 at 20:50
• Did you consider the congruence modulo $y=2x-1$ ? Without this, you cannot proof the claim. – Peter Nov 20 '15 at 20:55