# Thread: Order of Integer Questions

1. ## Order of Integer Questions

1) Show that if n is a positive integer and a and b are integers relatively prime to n such that $\displaystyle (ord_{n}a, ord_{n}b)$ = 1, then $\displaystyle ord_{n}(ab)$ = $\displaystyle ord_{n}a * ord_{n}b$

2) Let p be a prime divisor of the Fermat number $\displaystyle F_{n} = 2^{2n} + 1$
a) Show that $\displaystyle ord_{p}2 = 2^n + 1$
b) From part (a), conclude that $\displaystyle 2^{n+1} \mid (p-1)$, so that p must be of the form $\displaystyle 2^{n+1}k + 1$

2. For the first one...

(By the way Fermat's number is from the form: $\displaystyle 2^{2^n}+1$ when $\displaystyle n=0,1,...$

I don't use to work with $\displaystyle ord$ notation, so...

$\displaystyle ord_n(a)=t$, $\displaystyle ord_n(b)=s$ and $\displaystyle ord_{n}(ab) =w$

From $\displaystyle ord_{n}(ab)$ which can be written as:

$\displaystyle (ab)^w\equiv1(mod {n})$, we can deduce:

$\displaystyle (ab)^{wt}\equiv 1(mod {n})$, and from $\displaystyle (a)^{wt}\equiv 1(mod {n})$, we get:

$\displaystyle (b)^{wt}\equiv 1(mod {n})$

From your first theorem on this subject of orders... we can say that: $\displaystyle {s}\mid {wt}$, but $\displaystyle gcd(w,t)=1$, hence: $\displaystyle {t}\mid {w}$...

Similarly we can prove: $\displaystyle {s}\mid{w}$.

Now, we have: $\displaystyle {t}\mid {w}$ and $\displaystyle {s}\mid {w}$, hence: $\displaystyle {ts}\mid {w}$.

And the last part:

We have given that:

$\displaystyle a^t\equiv1(mod{n})$ and $\displaystyle b^s\equiv1(mod{n})$,
so: $\displaystyle (ab)^{ts}=(a^t)^s(b^s)^t\equiv1(mod{n})$ and from the theorem I mentioned before we get: $\displaystyle {w}\mid {ts}$, and with the $\displaystyle {ts}\mid {w}$ (from the last part), we may deduce that $\displaystyle w=ts$