7 Find the largest integer n such that there exists an odd i

7. Find the largest integer n such that there exists an odd integer with order equal to n mod 2^alpha.

Solution

This is a general solution which applies to every other problem similiar to this with order equal to n mod pq.

(Assuming that pq). We have an1(modpq) if and only if an1(modp) and an1(modq). In other words, the order of a modolo pq is the lcm of the orders modulo p and modulo q. The multiplicative groups modulo a prime are cyclic, hence there exists ap of order p1 modulo p. Similarly there exists aq of order q1 modulo q (and for all other elements, the order divides p1 resp. q1). By the Chinese Remainder Theorem, we find a with aap(modp) and aaq(modq). Then a has order

lcm(p1,q1)

and this is the maximum possible.