3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – user286813 Nov 19 '15 at 22:31
  • $\begingroup$ Put the exponent in { } e.g. b^{2x+1}. Use { }, not ( ) $\endgroup$ – Mirko Nov 19 '15 at 22:48
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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