Let $k$ be a positive integer such that $p=2k+1$ and $q=4k+1$ are both prime. Consider the number $$N=pq$$ I proved that for every positive integer $a$ coprime to $N$ we have $$a^{N-1}\equiv 1\mod N$$ if and only if $$(\frac{a}{q})=1$$ where the paranthesis denote the Legendre-symbol. Moreover , I proved $$a^{(N-1)/2}\equiv (\frac{a}{p})\mod p$$ and $$a^{(N-1)/2}\equiv (\frac{a}{q})\cdot a^{(q-1)/4} \mod q$$

I want to prove the following conjecture :

We have $$a^{(q-1)/4}\equiv (\frac{a}{p})\mod q$$ for exactly half of the numbers $a$ satisfying $(\frac{a}{q})=1$ and therefore in the case $p\equiv 3\mod 4$ for half of the bases $a$ satisfying $(\frac{a}{q})=1$ , $N$ passes the strong Fermat-pseudoprime-test. What else do I need to prove that a number of the form $N=(4k+3)(8k+5)$ with primes $4k+3$ and $8k+5$ has the maximum of $\frac{\varphi(N)}{4}$ bases $a$ for which $N$ passes the strong Fermat-pseudoprime-test ?


Your Answer

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

Browse other questions tagged or ask your own question.