# 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 $(ord_{n}a, ord_{n}b)$ = 1, then $ord_{n}(ab)$ = $ord_{n}a * ord_{n}b$

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

2. For the first one...

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

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

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

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

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

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

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

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

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

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

And the last part:

We have given that:

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