1
$\begingroup$

I am trying to determine whether there exists an integer $a$ such that $\text{ord}_{20}(a) = 8$. I know that if $(a,n) = 1$ and $n>0$, then $\text{ord}_{n}(a)\mid \phi(n)$. I cannot use any abstract algebraic techniques. I am only expected to know what primitive roots are, Euler's Theorem, and some other elementary number-theoretic principles related to congruences, linear diophantine equations, and Fermat's Little Theorem.

I understand that I can answer this question by going through each of $1,2,3,\ldots,20$ and checking to see if each raised to the power of $8$ is congruent to $1$ mod 20. However, there is probably a faster way to do this and I am looking for help from the StackExchange community on how to do that. Thank you in advance.

$\endgroup$
  • $\begingroup$ This question might set a good context to study Carmichael function and its properties. At the very least, you could study what the carmichael function does and how it relates to this problem. It's quite elementary. $\endgroup$ – rah4927 Jun 18 '15 at 17:59
1
$\begingroup$

Let $a$ be an integer coprime with $20$. Then $a$ is coprime with both $4$ and $5$.

By the Fermat—Euler theorem, we have $a^2 \equiv 1 \bmod 4$ and $a^4 \equiv 1 \bmod 5$.

By the Chinese Remainder theorem, these congruences imply $a^4 \equiv 1 \bmod 20$.

Hence, there is no integer having order $8$ mod $20$.

$\endgroup$
  • $\begingroup$ What does $U(20)$ mean? I am not familiar with this notation. Also, am I right to assume that the equals-sign with the squiggly line on top of it is a group isomorphism symbol? In any case, like I said in my question, I cannot use any techniques from abstract algebra. $\endgroup$ – letsmakemuffinstogether Jun 18 '15 at 3:18
  • $\begingroup$ Also you meant to say $U(5)$ has order 4" and not $U(4)$ has order 2 and order 4". $\endgroup$ – letsmakemuffinstogether Jun 18 '15 at 3:18
  • $\begingroup$ I"m afraid I find your answer utterly opaque. Can you please provide some context for what $g$ is? Also, that's false since $g^2 \equiv 0 \not \equiv 1$mod $4$. $\endgroup$ – letsmakemuffinstogether Jun 18 '15 at 3:22
  • $\begingroup$ Okay your answer is much clearer now. However, I don't see how it's general enough. In your proof, you have assumed that $g$ is coprime to 20 and we have not ruled out the possibility that those $g$ which are not coprime with 0 will not be congruent to 1 modulo 20. $\endgroup$ – letsmakemuffinstogether Jun 18 '15 at 3:58
  • $\begingroup$ @letsmakemuffinstogether, order is defined only for integers coprime with the modulus. Also, $g^k \equiv 1 \bmod m$ implies $(g,m)=1$. $\endgroup$ – lhf Jun 18 '15 at 11:38
-1
$\begingroup$

No there does not exists any such element. Because if $\exists~ a\in U_{20} $ then since order $U_{20} $ is $\phi(20)=\phi(2^2.5)=8$ which shows that $U_{20} $ is cyclic group. This is a contradiction since we know that only $\displaystyle U_{p^n}~\&~U_{2p^n}$ where $p$ is odd prime , are cyclic groups.

$\endgroup$
  • $\begingroup$ Okay thank you but just as I said above, I cannot use any methods from abstract algebra. None whatsoever. $\endgroup$ – letsmakemuffinstogether Jun 18 '15 at 3:20

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.