I'm trying to solve the following two problems:

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


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)

  • $\begingroup$ 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). $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – mathmath8128 Oct 14 '11 at 23:58
  • $\begingroup$ @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. $\endgroup$ – 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}$.

  • $\begingroup$ 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.... $\endgroup$ – mathmath8128 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.