What residues?

7 x 25 10 83 \large{\dfrac{7x^{25}-10}{83}}

Find the smallest positive integer x {x} for which the above expression is also an integer.


The answer is 69.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Sean Sullivan
Jul 27, 2015

We have 7 x 25 10 0 m o d 83 7x^{25}-10\equiv0\mod83 so 7 x 25 10 m o d 83 7x^{25}\equiv10\mod83

letting n = x 25 n=x^{25} :

7 n = 10 + 83 m 7n=10+83m then 83 m 10 m o d 7 83m\equiv-10\mod 7

Simplifying gives m 4 m o d 7 m = 3 m o d 7 -m\equiv4\mod7 \implies m=3 \mod7

Now 7 n = 10 + 83 ( 3 ) = 259 n = 37 7n=10+83(3)=259 \implies n=37

So x 25 = 37 m o d 83 x^{25}=37\mod 83

Fermat's Little Theorem tells us 3 7 82 1 m o d 83 37^{82}\equiv1\mod83 and by rules of exponents ( 3 7 82 ) r 37 37 m o d 83 (37^{82})^{r}37\equiv37\mod83

We want the exponent on 37 37 on the left to be divisble by 25 25 so 82 r + 1 0 m o d 25 82r+1\equiv0\mod25 and then 7 r 24 m o d 25 7r\equiv24\mod25 which means 7 r = 25 s + 24 7r=25s+24 and subsequently that 25 s + 24 0 m o d 7 25s+24\equiv0 \mod 7 .

Now 4 s 3 4 m o d 7 s 1 m o d 7 4s\equiv-3\equiv4 \mod 7 \implies s\equiv1\mod7

Now 7 r = 25 ( 1 ) + 24 = 49 7r=25(1)+24=49 and r = 7 r=7

This gives us ( 3 7 82 ) 7 37 37 m o d 83 (37^{82})^{7}37\equiv37\mod83 or 3 7 575 37 m o d 83 37^{575}\equiv37\mod83

This is equivalent to ( 3 7 23 ) 25 37 m o d 83 (37^{23})^{25}\equiv37\mod83 and x 3 7 23 m o d 83 x\equiv37^{23} \mod83

x 3 7 23 ( 3 7 2 ) 11 37 4 1 11 37 2 1 5 41 37 3 5 7 5 41 37 ( 2 ) 3 7 5 41 37 3 7 5 37 28 7 5 1 5 2 7 2 2 2 2 69 m o d 83 x\equiv37^{23}\equiv(37^{2})^{11}\cdot37\equiv41^{11}\cdot37\equiv21^{5}\cdot41\cdot37\equiv3^{5}\cdot7^{5}\cdot41\cdot37\equiv(-2)\cdot3\cdot7^{5}\cdot41\cdot37\equiv3\cdot7^{5}\cdot37\equiv28\cdot7^{5}\equiv15^{2}\cdot7^{2}\equiv22^{2}\equiv\boxed{69}\mod83

This last line is probably a little inefficient but it is just a matter of simplifying the product and this is the method I used

Lu Chee Ket
Oct 21, 2015

69 [x^y] 25 [*] 7 [-] 10 [=] [MOD] 83 [=] gives 0.

Answer: 69

John Gilling
Jul 27, 2015

It is simple (albeit tedious) to show that the element 2 generates the group of units (mod 83), especially since 82 = 2*41 factors so simply. From this point we can solve Satyajit's congruence with a table of indices (i.e. logarithms).

That being said, I'd love to know if there is a slicker way to attack this problem.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...