0

I mean, can someone show me the general approach to solve exercises like this one? I've seen here that many questions related to this were asked but no one showed the step by step approach. Thank you

gt6989b
  • 54,422
Osmion
  • 9
  • 1
  • Partial lead on an answer, re I don't know the full analytical solution, so I might have to resort to brute force: [1] First consult Fermat's Little Theorem. [2] Then, consider that $(28)$ is a multiple of $(7)$. – user2661923 Apr 07 '22 at 16:54
  • Which were the related questions where nobody showed a step-by-step approach? If you link to them in your question and say what was missing, it will help people understand what you are trying to ask for. – David K Apr 07 '22 at 16:56
  • With numbers as small as this, trial and error is as good as anything. – lulu Apr 07 '22 at 16:56
  • Trial and error signifying, for $x \in {1,2,\cdots,28},$ compute $x^7 \pmod{29}.$ – user2661923 Apr 07 '22 at 16:57

4 Answers4

1

In order to solve this question you should be familiear with the notion of primitive root and index.

We need to solve the following congruence $x^7\equiv 1 \pmod {29}$.

We see that $\varphi(29)=28$ and $\text{gcd}(7,28)=7$ and $\text{ind}1=0$. Since $7\mid \text{ind}1$, then this congruence is solvable and has 7 solutions.

The above congruence is equivalent to $7\text{ind}x\equiv \text{ind}1 \pmod{28}$ which is the same as $\text{ind}x\equiv 0\pmod{4}$. It implies that $\text{ind}x=4,8,12,16,20,24,0$. Hence $x\equiv 1,24,7,25,23,20,16 \pmod{29}$

RFZ
  • 16,814
1

By Fermat's little theorem, any $y$ not divisible by $29$ satisfies $y^{28} \equiv 1 \bmod{29}$. So $x=y^4$ satisfies $x^7 \equiv 1 \bmod{29}$. If moreover $y^4 \not\equiv 1\bmod{29}$, then the powers $x,x^2,\ldots,x^7\equiv 1$ give all seven solutions to the congruence. (That there are indeed seven solutions needs some knowledge about the structure of the group of units modulo $29$, which I won't go into any further.)

So let's try $y=2$, which certainly satisfies $y^4 \not\equiv 1\bmod{29}$. We then have the solutions $x=16$, $x^2=24$, $x^3=7$, $x^4=25$, $x^5=23$, $x^6=20$, $x^7=1$.

R.P.
  • 1,306
0

I'm sure there are more elegant approaches, but one way that uses a minimal amount of brute force is to note that this is the same thing as saying $x^8$ is congruent to $x$ mod 28, and $x^8=((x^2)^2)^2$. So if you compute the 30 quadratic residues (i.e. what $x^2$ is congruent to, mod 29) once, you can then feed the input into that output two more times and look for anywhere you get the same results.

In excel,one way to do this step by step is by generating a first column that is the numbers 0-29, the second is their squares with the formula B1=A1^2 (and filling the rest). The third is C1=mod(A1,29) to get the residues after squaring. Then the fourth is D1=vlookup($A$1,$C$30,C1,3). This takes the result of $x^2$ after modding by 29 and then gives you the result of squaring it and modding by 29 again. Fill that formula down, then do the same once more: E1=vlookup($A$1,$C$30,D1,3). Now we have a column of the result of $x^8$ mod 29, and we just need to look where the numbers are equal to column A. If we are really lazy, we can even column a 6th column: f1=if(a1=e1,a1). This will give false for all the bad values and the number for all the true values, yielding 0,1,7,16,20,23,24,25.

Alan
  • 16,582
0

Note that $29-1=28=4\times 7$, Fermat's little theorem:

$x^{29-1=28}\equiv 1 \bmod 29$

taking fourth root we get:

$(x^{28})^{\frac 14}\equiv (1)^{\frac 14}\bmod 29$

Or:

$X^7\equiv 1 \bmod 29$

that is x can be any number with no common factor with 29( or is co-prime with 29).

sirous
  • 10,751