2
$\begingroup$

I am studying for an algebra final exam and would like to check if the way I solved this exercise is ok. I have been asked to:

Find all the positive divisors of $25^{70}$ with remainder $2 \pmod 9$ and with remainder $3 \pmod{11}$.

I started by noticing that I can write $25^{70}$ as $5^{140}$ and that finding all the positive divisors means to consider all the $n$ such that $n|5^{140}$.

I can write those as $n=5^\alpha$ with $0\leq\alpha\leq140$

This means that there are $141$ positive divisors.

Then, I wrote:

$5^{\alpha} \equiv2\pmod{9}$

$5^{\alpha} \equiv3\pmod{11}$.

After that, I checked all the $\alpha$ that satisfy $5^{\alpha} \equiv2\pmod{9}$ and those that satisfy $5^{\alpha} \equiv3\pmod{11}$ simultaneously.

I noticed that for the first term of the system, those such $\alpha$ are $\alpha \equiv5\pmod{6}$, and for the second term they are $\alpha \equiv2\pmod{5}$

To finish, I considered a new system:

$\alpha \equiv5\pmod{6}$

$\alpha \equiv2\pmod{5}$.

And concluded that, by Chinese Remainder Theorem, those are the $\alpha \equiv17\pmod{30}$. Since we said that $0\leq\alpha\leq140$, those such $\alpha$ must be $\alpha=\{ {17, 47, 77, 107, 137}\}$

There are two things I am not sure about: the first one is the way I discovered those $\alpha$. I have to consider too many of them (they are $141$), but I ended up realizing 'by hand' that the cycle was shorter. Am I doing something wrong? Is there another method?

The other thing I am not quite sure about is if I am using properly the conditions I have been given with the positive divisors.

I would appreciate any help.

Thanks.

$\endgroup$
6
  • $\begingroup$ Euler's generalization of Fermat's Little Theorem gives $5^{\phi(9)} = 5^6 \equiv 1 \pmod{9}$; and FLT itself gives $5^10 \equiv 1 \pmod{11}$. $\endgroup$ – Daniel Schepler Jun 17 '17 at 16:07
  • $\begingroup$ Hello, @DanielSchepler. I did notice that FLT gives $5^{10} \equiv1\pmod{11}$ and, therefore, gives me a cycle. Also, I noticed that $5$ instead of $10$ is a shortened cycle (since FLT gives a multiple of the cycle). We did not study Euler's generalization, that's why I didn't use it. What I was wondering was if the proof is correct and if my method is adequate. $\endgroup$ – Esteban Sargiotto Jun 17 '17 at 16:23
  • $\begingroup$ Note $\, {\rm mod}\ 11\!:\ 5\equiv 4^2\,\Rightarrow\, 5^5\equiv 4^{10}\equiv 1,\,$ by Fermat. See Euler's criterion. Have you learned yet about the (multiplicative) order of elements? $\ \ $ $\endgroup$ – Bill Dubuque Jun 17 '17 at 17:24
  • $\begingroup$ Hi @BillDubuque , for what I understood, using the Euler's $\phi$ function is a faster way to find the cycle and it is useful when I can't use Fermat since the number is not a prime. Nevertheless, no, I have not yet learned about the multiplicative order of elements. I am supposed to use FLT and the Chinese Remainder Theorem, apart from basic knowledge of congruences, divisibility, prime factorization and its properties $\endgroup$ – Esteban Sargiotto Jun 17 '17 at 17:54
  • 1
    $\begingroup$ Yes, for non-prime moduli you can use Euler's phi (or better, Carmichael's lambda). Once you learn about orders and/or group/ideal theory this will all become clearer. $\endgroup$ – Bill Dubuque Jun 17 '17 at 18:10
2
$\begingroup$

Your solution is correct. Below, I've provided some further explanation as to how exactly it works.

Say we want to find all $\alpha\in\mathbb{N}$ with $5^\alpha\equiv 2\pmod 9$. Given any two $\alpha,\beta\in\mathbb{N}$ with $5^\alpha\equiv 2\pmod 9$ and $5^{\alpha+\beta}\equiv2\pmod 9$,we have $5^\beta\equiv 1\pmod 9$. On the other hand, if given some $\alpha,\beta\in\Bbb{N}$ with $5^\alpha\equiv 2\pmod 9$ and $5^{\beta}\equiv 1\pmod 9$, we have $5^{\alpha+\beta}\equiv 2\pmod 9$.

Also, if we have two $\alpha,\beta$ with $5^\alpha\equiv 1\pmod 9$ and $5^{\beta}\equiv 1\pmod 9$, we would have $5^{\gcd(\alpha,\beta)}\equiv 1\pmod 9$. Therefore there exists some $d\in\mathbb{N}$ such that $5^\alpha\equiv 1\pmod 9$ if and only if $d\mid \alpha$.

Combining these results gives that $5^\alpha\equiv 2\pmod 9$ if and only if $\alpha \equiv \beta\pmod d$ for some $\beta$ with $5^\beta\equiv 2\pmod 9$.

We find that when working modulo $9$, we can take $d=6$ (simply the smallest positive integer $d$ such that $5^d\equiv 1\pmod 9$) and an example of a solution would be $5$. Putting $d=6$ and $\beta=5$, this gives: $$\alpha\equiv 5\pmod 6$$ You can do the same for the other congruence.

$\endgroup$
2
  • $\begingroup$ You have some typos: I suppose you mean $5^\beta\equiv 1\pmod\color{red}{11}$, not mod β. But I don't see why would have $5^{\gcd(\alpha,\beta)}\equiv 1 \mod9$. $\endgroup$ – Bernard Jun 17 '17 at 18:44
  • $\begingroup$ @Bernard If $5^\alpha\equiv 5^{\beta}\equiv 1\pmod 9$, then $5^{\gcd(\alpha,\beta)}\equiv 1\pmod 9$ follows from Bezout's identity. $\endgroup$ – Mastrem Jun 17 '17 at 18:48
2
$\begingroup$

Usin the Chinese Remainder theorem, we have to solve for \begin{cases}5^n\equiv 2\mod9,\\5^n\equiv 3\mod11.\end{cases} You won't have to examine so many cases, since by Euler's theorem, $5$ has order a divisor of $\varphi(9)=6$ modulo $9$, and a divisor of $\varphi(11)=10$ modulo $11$.

Calculating the successive powers of $x$ mod. $9$ and mod. $11$, we see that $5$ has indeed order $6$ mod $9$, but order $5$ mod $11$, so you only have to calculate $30$ modular powers of $5$, and as you found the values $2$ and $5$, you obtain $$\begin{cases} 5^n\equiv2\mod 9\phantom{1}\iff n\equiv 5\mod6,\\5^n\equiv 3\mod 11\iff n\equiv 2\mod 5.\end{cases}$$ The solutions result from a Bézout's relation between $6$ and $5$, especially simple here: $\;6-5=1$, so the solutions satisfy $$n\equiv 2\cdot 6-5\cdot 5=-13\mod \operatorname{lcm}(6,5)=30.$$ The smallest positive value is $17$, and the solutions at most equal to $140$ are $$\{17,47,77,107,137\}.$$

$\endgroup$

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.