1 vote

Prove that if $e.d \equiv 1 \bmod (p-1)(q-1)$ then it’s impossible to have $e.d \equiv 1 \bmod pq$

The statement you have given appears to be false. A counterexample which first strung to my mind is $e = 31$ and $d = 27791$. Taking $p = 89, q = 11$, we get $e*d$ congruent to both $1$ mod $(p*q)$ ...
DrDoofenshmirtz's user avatar
1 vote

Is there a formula that counts the number of positive odd integers up to a given integer N that are relatively prime to N.

Let f(n) = count of all co-prime integers and g(n) = count of odd co-prime integers. If n is even then all co-prime numbers are odd, so f(n) = g(n). For odd n: If k is co-prime to 2n then so is 2n-k, ...
gnasher729's user avatar
  • 9,647

Only top scored, non community-wiki answers of a minimum length are eligible