0

Why is it if we use 1 2 3 4 mod 5 and we take x^3 of these numbers, we come to: 1 3 2 4 (all numbers are different as you can see)? Why are they all different. Thanks

Explanation: $a^{\phi(p)} \equiv 1 \pmod{p}$ if $a$ and $p$ are relatively prime. You know that $\phi(5) = 5 - 1 = 4$, so if the exponent - say $k$ - is relatively prime to $4$, then the values of $x^k$ for $x \in {1, 2, 3, 4}$ will be all different. How can we conclude from $a^{\phi(p)} \equiv 1 \pmod{p}$ that all numbers are different?

Daniel Fischer
  • 206,697
Jeck Coeler
  • 1

3 Answers3

1

We have by Euler's theorem that $a^{\phi(p)}\equiv1\pmod p$ if $(a,p)=1$,

so, if $bc\equiv1\bmod\phi(p)$, then $(a^b)^c=a^{bc}\equiv a^1=a\pmod p$,

so the map $a\mapsto a^b$ is invertible ($a\mapsto a^c)$ and therefore bijective.

For your particular example, take $p=5$, $\phi(p)=4$, $b=3$, and $c=3$.

Then the map $a\mapsto a^3$, which takes $1\mapsto1, 2\mapsto3, 3\mapsto2, $ and $4\mapsto4$ is its own inverse:

$$1\mapsto1\mapsto1, 2\mapsto3\mapsto2, 3\mapsto2\mapsto3, \text{ and } 4\mapsto4\mapsto4.$$

If the map were not one-to-one, it could not be inverted.

J. W. Tanner
  • 60,406
0

A simple explanation with Lagrange's theorem:

You have to show the map $x\mapsto x^3$ is injective in the multiplicative group $(\mathbf Z/5\mathbf Z)^\times$. As it is a group homomorphism because the group is commutative, it amounts to showing its kernel is $\{1\}$.

Consider $x\in\{1,2,3,4\}$ such that $x^3=1$. This implies the order of $x$ is a divisor of $3$. But as it is an element of the group $(\mathbf Z/5\mathbf Z)^\times$, of order $4$, it is also, by Lagrange, a divisor of $4$, and $\gcd(3,4)=1$. Therefore, necessarily, we have $x=1$.

Some details:

Denote, for any $x\in(\mathbf Z/5\mathbf Z)^\times$, $o(x)$ (the order of $x$) the least positive integer $k$ such that $x^k\equiv 1\mod 5$. It is easy to show that if $x^\ell\equiv 1\mod 5$, then $\ell$ is a multiple of $o(x)$.

Now suppose $x^3\equiv y^3\mod 5$. If we denote $y^{-1}$ the inverse of $y\bmod 5$, this implies that $x^3(y^3)^{-1}=\bigl(xy^{-1}\bigr)^3\equiv 1\mod 5$. By the property mentioned in the above §, $3$ is a multiple of $o(xy^{-1})$. Since $3$ is prime, this order is therefore either $1$ or $3$.

However, one can show that this order is also a divisor or $\#(\mathbf Z/5\mathbf Z)^\times$, which is $4$. As $3\not\mid 4$, the only solution is $\;o(xy^{-1})=1$, which means, by definition, that $xy^{-1}=1$, whence, multiplying both sides by $y$, $x=y$.

Bernard
  • 175,478
  • Do you at least know what is the order of an element in $\mathbf Z/p\mathbf Z$? – Bernard Jan 26 '20 at 00:31
  • unfortunately, no. – Jeck Coeler Jan 26 '20 at 00:32
  • What do you know about this last set? – Bernard Jan 26 '20 at 00:36
  • I know nothing about number theory. Can we not proof it by saying that there are two different x that map to the same residue and then proof a contradiction? – Jeck Coeler Jan 26 '20 at 00:37
  • That's more or less what I had in mind when I mentioned the kernel and the order of the element. I'll try to post a sketch of the details, which you should check by yourself – and ask questions if necessary. – Bernard Jan 26 '20 at 00:43
  • thank you very much. Will you do it now? – Jeck Coeler Jan 26 '20 at 00:44
  • 'Tis done${ }$. – Bernard Jan 26 '20 at 01:00
  • I understood everything, but not "It is easy to show that if xℓ≡1mod5, then ℓ is a multiple of o(x)." Can you explain why it is the case? – Jeck Coeler Jan 26 '20 at 10:13
  • It is linked to euclidean division in $\mathbf Z$: divide $\ell$ by $o(x)$: you have a quotient $q$ and a remainder $r$ satisfying the relation $\ell=q\cdot o(x)+r,\quad 0\le r<o(x)$, so $x^\ell=\bigl(x^{o(x)}\bigr)^q,x^r$, i.e. $;1=1^q, x^r$. However, if $r>0$, $x^r=1$ contradicts the minimality of $o(x)$. Therefore $r=0$, which means that $o(x)$ divides $\ell$. This is exactly the way one proves that all ideals of $\mathbf Z$ are principal, if that is meaningful to you. – Bernard Jan 26 '20 at 10:34
  • x^3≡y^3 mod5 <=>(xy^−1)^3≡1 mod5 3 is a multiple of o(xy−1). Since 3 is prime, this order is therefore either 1 or 3. I now just need an easier way to show that the only corect one is 1. Can't I prove it on a much easier way? Like with the Euler's theorem that a^4≡1 or just something much easier that can show that 1 is the only correct answer? – Jeck Coeler Jan 26 '20 at 10:44
  • Euler's theorem (actually Fermat's theorem) tells you the order of all nonzero elements is a divisor of $4$, so it can't be $3$. Everything relies on the notion of order of an element (which, incidentally, is a notion the group theory). – Bernard Jan 26 '20 at 10:52
  • each of your comments gets more and more difficult. I am not porfessional. You say the order of all nonzero elements is a divisor of 4. Let's take 3^3 with order 3, is equal to 9 and is not a divisor of 4. Please explain it clearly I don't understand anything about the notions you use. – Jeck Coeler Jan 26 '20 at 10:55
  • We have by Euler's theorem that a^ϕ(p)≡1(modp) if (a,p)=1. So in my case they are all equal to 4? because ϕ(p)=4. Why did you say DIVISORS of 4? – Jeck Coeler Jan 26 '20 at 11:00
  • I'm afraid you're confusing the order of an element (the least positive integer such that …) and the exponent. We indeed have $3^2\equiv 4\bmod 5$, $3^3\equiv 2\bmod 5$ and $3^4\equiv 4^2\equiv 1\bmod 5$, so the order of $3$ is $4$. – Bernard Jan 26 '20 at 11:01
  • Because the order is the least exponent having this property. When you have an exponent with the property, you cannot say a priori it is the least. For instance $2$ and $3$ indeed have order $4$, but $4$ has order $2$. – Bernard Jan 26 '20 at 11:04
  • Euler's theorem (actually Fermat's theorem) tells you the order of all nonzero elements is a divisor of 4. 1) I still don't understand what an order is. 2) When did he say that? He is talking about the exponent ϕ(p) and not about orders. Please don't use difficult names and notations, explain it simply. – Jeck Coeler Jan 26 '20 at 11:13
  • And AGAIN: I know NOTHING about number theory. – Jeck Coeler Jan 26 '20 at 11:23
  • Did you follow the computations in my last but one comment? As to the difficulty of names/notations, it is easier to understand a notion or a notation than reading endlessly a circumlocution. In geometry, you don't repeat ad nauseam ‘ a quadrilateral with pairwise parallel sides’, you simply say a parallelogram. Can't you make this very little effort? – Bernard Jan 26 '20 at 11:23
  • I suppose you know at least what congruences are, since you use Euler and Fermat's theorems. – Bernard Jan 26 '20 at 11:24
  • Yes, congruence I know. – Jeck Coeler Jan 26 '20 at 11:25
  • The order of an element x in a group G is the smallest positive integer n for which x^n is the identity element. What is an 'identity element'? – Jeck Coeler Jan 26 '20 at 11:25
  • The multiplicative unit – the congruence class of $1$ in the present case. – Bernard Jan 26 '20 at 11:27
  • x^3≡y^3 mod5 <=>(xy^−1)^3≡1 mod 5 all I have to do now is proof that xy^-1 is equal to 1 – Jeck Coeler Jan 26 '20 at 11:38
  • With the notion of order, this is obvious. This being said, as there are only $4$ elements, it is not long to check that a single element has a cube equal to one. Of course, if you prime number were $541$, it would be a bit longer… and you would see clearly why thinking can be more fruitful than computing. – Bernard Jan 26 '20 at 11:46
  • Can't I just say that x^3 ≡ y^3 (mod 29) ⟺ (xy^-1)^3 ≡ 1 (mod 29) ⟺ xy^-1=29n – Jeck Coeler Jan 26 '20 at 12:04
  • and now proof that x=y? – Jeck Coeler Jan 26 '20 at 12:04
  • $x^3\equiv y^3\implies( x^3)^{19}\equiv(y^3)^{19}\iff x^{57}\equiv y^{57}$. Now $57\equiv1\mod \varphi(29)$ so $x\equiv x^{57}\equiv y^{57}\equiv y\mod 29$ (by Fermat). – Bernard Jan 26 '20 at 12:29
  • But you just combined mod φ(29) with mod29... maybe mod φ(29)(=28?) it is 1, but why is it one if we go to mod 29? – Jeck Coeler Jan 26 '20 at 12:48
  • Euler's theorem can be written as $a^{N}\equiv a^{N\bmod\varphi(n)}\mod n$ for any $a$ coprime to $n$ since $a^{\varphi(n)}\equiv 1\mod n$. – Bernard Jan 26 '20 at 13:02
0

There are a few explanations:

  • multiplicative inverses ( modular equivalent to reciprocal (division of 1 by a number)) are unique when defined.

  • $a^n=-(-a)^n$ when $n$ is odd. as congruence is a weakened version of equality, it follows this rule as well.

The way the above congruence flows into this is if they are congrurnt to 1, decreasing the exponent by 1 is taking the multiplicative inverse.