Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  mathmath8128 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}$.

share|improve this answer
    
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.... –  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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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