# Trouble with elementary number theory

I'm trying to solve the following two problems:

Show $n^{12}\equiv 1\pmod{72}$ when $(72,n)=1$

and

Compute ${7^8}^9\pmod{100}$

For the first, I saw that $n^{24}=n^{\varphi(72)}\equiv1\pmod{72}$ by Euler's theorem, but this leaves us with $n^{12}n^{12}\equiv 1\pmod{72}$. This could mean $n^{12}\equiv 1\pmod{72}$ or $n^{12}\equiv 71\pmod{72}$. I'm not sure how to argue correctly to conclude it's only $n^{12}\equiv 1\pmod{72}$.

For the second one, I practically did brute force. ${7^8}^9\pmod{100}$ can be solved by considering $8^{9}\pmod{\varphi(100)=40}$. Since $8$ is cyclic with order $4: 8^5\equiv 8\pmod{40}$, we know $8^9=8^5\cdot8^4\equiv 8^5\equiv 8$. So look at $7^8\pmod{100}$. 7 is also cyclic with $7^4\equiv 1\pmod{100}$. So $7^8=(7^4)^2\equiv 1\pmod{100}$. I knew these "cyclic" things by manually computing and reducing, though.

Thank you for any help... (note this is not homework)

-
For the first problem, I find it easier to work separately with modulus $8$ and modulus $9$. We have $n^{\varphi(8)} =n^4 \equiv 1 \pmod{8}$, and $n^{\varphi(9)} =n^6 \equiv 1 \pmod{9}$, which yields our result. For the second problem, you will find it a little easier to work modulo $4$ (easy!) and $25$ (less pleasant). –  André Nicolas Oct 11 '11 at 4:33

For problem 2, you can do better than manually checking by using the Chinese Remainder Theorem.

Indeed, you first want to compute $x^9$ modulo $\phi(100)=\phi(2^2\times 5^2) = 2\times 4\times 5$. But working modulo $40$ is equivalent, by the Chinese Remainder Theorem, to working modulo $8$ and modulo $5$. The advantage is that $8^9\equiv 0 \pmod{8}$, and $8^9 \equiv 8\pmod{5}$ (since $\varphi(5)=4$, so $8^4\equiv 1\pmod{5}$). Since $8^9\equiv 8\pmod{8}$ and $8^9\equiv 8\pmod{5}$, then it follows that $8^9\equiv 8\pmod{40}$.

Then you can do the same thing with $7^8\pmod{100}$. Working modulo $4$ we have $7^8\equiv (-1)^8 \equiv 1\pmod{4}$, and working modulo $25$ we have $7^8\equiv (49)^4\equiv (-1)^4\equiv 1\pmod{25}$. So $7^8\equiv 1\pmod{100}$, and we are done.

The first problem is likewise simpler to do by working modulo $8$ and modulo $9$ separately, and then applying the Chinese Remainder Theorem.

-
Magidin: Thanks as always for all your replies! Sorry it's taken so long for me to reply; school has been busy. I understand that the Chinese remainder theorem gives us conditions on the solution of simultaneous linear congruences (modulo the product of the moduli), but I don't understand how we can separate (mod 40) into looking at (mod 5) and (mod 8)? Is it that, since we are looking for $x\pmod{100}$, we can look at $x\pmod{25}$ and $x\pmod{4}$ since $(4,25)=1$ and simplify the problem? I think I understand... we never covered this in class so I'm just verifying. –  ae0709 Oct 14 '11 at 23:58
@aengle: The Chinese Remainder Theorem says that solving a congruence $x\equiv k\pmod{mn}$, where $m$ and $n$ are coprime, is equivalent to solving the pair of congruences $x\equiv k\pmod{m}$ and $x\equiv k\pmod{n}$. That a solution modulo $mn$ gives solutions modulo $m$ and solutions modulo $n$ is immediate. If you have a solution modulo $m$, call it $a$, and a solution modulo $n$, call it $b$, then the CRT tells you that you can find a unique $x$ modulo $mn$ such that $x\equiv a\pmod{n}$ and $x\equiv b\pmod{n}$. Since $\gcd(m,n)=1$ implies ($m|r\land n|r\implies mn|r$), this does it. –  Arturo Magidin Oct 15 '11 at 2:09

For the first one, note that, even though $\phi(8)=4$, it is in fact true that $\gcd(n,8)=1$ implies $n^2\equiv1\pmod8$. If you think it through, you'll see that that's why you can get away with 12 when working mod 72, instead of needing 24.

EDIT: elaboration in response to OP's comment:

$\gcd(n,8)=1$ implies $n^2\equiv1\pmod8$ which implies $n^6\equiv1\pmod8$.

$\gcd(n,9)=1$ and $\phi(9)=6$ implies $n^6\equiv1\pmod9$.

The last two congruences imply $n^6\equiv1\pmod{72}$, which certainly implies the required $n^{12}\equiv1\pmod{72}$.

-
I know it's been a while, but I'm trying to understand your statement. It seems you're avoiding the chinese remainder theorem, but I don't know what you exactly mean. I guess I am not thinking it through well enough.... –  ae0709 Dec 6 '11 at 0:01

$(1)$ Using Carmichael function, $$\lambda(72)=\text{lcm}(\lambda(8),\lambda(9))=\text{lcm}(2,6)=6$$

$$\implies n^6\equiv1\pmod{72}\text{ if }(n,72)=1$$

$(2)$ Observe that $\displaystyle7^2=49=50-1\implies 7^4=(50-1)^2=50^2-2\cdot50\cdot1+1\equiv1\pmod{100}$

$\displaystyle\implies7^n\equiv1\pmod{100}$ if $4|n$

Now, $8^9=(2^3)^9=2^{27}$

-