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.

The problem comes from a practice final for a final exam I have later today.

It says "Show that if $\gcd(e, 24) = 1$ then $e^2 \equiv 1 \bmod 24$".

I found that Euler's totient function $\phi(24) = 8$ So I now know $e^8 \equiv 1 \bmod 24$, but I'm not sure where to go from there.

I found that if $\sqrt[4]e$ is an integer, then it's obvious that $\sqrt[4]e \mid e$, so $\gcd(\sqrt[4]e, 24) = 1$ which I can use to prove $e^2 \equiv 1 \bmod 24$, but that only proves it in the case where $\sqrt[4]e$ is an integer (and I don't think I'm really going in the right direction here).

share|improve this question

4 Answers 4

up vote 13 down vote accepted

Euler's $\varphi$-function is often not the right tool for this kind of problem. I would work separately modulo $3$ and modulo $8$.

If $\gcd(e,24)=1$, then $\gcd(e,3)=1$. Therefore, by Fermat's Theorem (but that's overkill!) we have $e^2\equiv 1\pmod 3$. It is overkill because if $e$ is not divisible by $3$, then $e\equiv \pm 1\pmod{3}$, and therefore $e^2\equiv 1\pmod 3$.

If $\gcd(e,24)=1$, then $e$ is odd. It is a standard fact that if $e$ is odd, then $e^2\equiv 1\pmod 8$. For a low level proof, all we need to do is to check the result for $e=1$, $3$, $5$, and $7$, or more simply for $e=\pm 1$ and $e=\pm 3$. Or else we can note that if $e$ is odd, then $e=2k+1$ for some $k$. Thus $e^2=4k^2+4k+1=4k(k+1)+1$. Since $k$ and $k+1$ are consecutive integers, one of them is even, and therefore $4k(k+1)$ is divisible by $8$.

From the facts that $e^2\equiv 1\pmod 3$ and $e^2\equiv 1\pmod 8$, we conclude that $e^2\equiv 1\pmod{24}$.

share|improve this answer
    
Thanks! That helps a lot –  Paulpro Dec 17 '11 at 17:26
5  
To see that $e^2\equiv 1\pmod 8$ for $e$ odd, you can do the following simple argument: $e^2-1=(e-1)(e+1)$ is the product of two consecutive even numbers. Thus one must be a multiple of $4$ and the other is even.... –  N. S. Dec 17 '11 at 19:23

The answer by Andre Nicolas is the way to go. However always bear in mind that you could have just checked this by hand, because the modulus of the problem ($24$) is rather small!

If $\gcd(e,24)=1$, and we are going to compute a value modulo $24$, then it suffices to check that the statement is true for those all congruence classes $e\bmod 24$ such that $\gcd(e,24)=1$, i.e., we need to check the statement for $$e\equiv 1,5,7,11,13,17,19,23 \bmod 24.$$ Now the problem has been reduced to checking that the square of each one of these eight numbers is congruent to $1\bmod 24$. Indeed: $$1^2\equiv 1,\ 5^2\equiv 25\equiv 24+1\equiv 1,\ 7^2\equiv 49\equiv 48+1\equiv 1,\ 11^2\equiv 121 \equiv 24\cdot 5+1\equiv 1 \bmod 24,$$ and $$23^2\equiv (-1)^2\equiv 1^2\equiv 1,\ 19^2\equiv (-5)^2\equiv 5^2\equiv 1,\ 17^2\equiv (-7)^2\equiv 7^2\equiv 1,\ 13^2\equiv (-11)^2 \equiv 1 \bmod 24.$$ Thus, $e^2\equiv 1 \bmod 24$ whenever $\gcd(e,24)=1$.

share|improve this answer
    
You can check 11 without even calculating it: $11^2=(12-1)^2=12^2-2*12+1= M24+1$. –  N. S. Dec 17 '11 at 23:33

Say $gcd(e, 24) = 1$. Since $24 = 2^3 \times 3$, we know $e$ is not even and not a multiple of 3. So $e$ is of form $6k \pm 1$, for some integer $k$.

Then $$(6k \pm 1)^2 = 36k^2 \pm 12k + 1$$ and so it suffices to show that $36k^2 + 12k$ is a multiple of $24$. We can factor it as $12k(3k+1)$; for any choice of $k$, one of $k$ and $3k+1$ is even, so $k(3k+1)$ is even, and $12k(3k+1)$ is a multiple of 24.

share|improve this answer

A more sophisticated answer is that $U_{24} \cong U_8 \times U_3 \cong C_2 \times C_2 \times C_2$, and so has exponent $2$.

In general, the exponent of $U_m$ is $\lambda(m)$, where $\lambda$ is Carmichael's function.

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.