# Help with congruences and positive divisors

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.

• 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}$. – Daniel Schepler Jun 17 '17 at 16:07
• 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. – Esteban Sargiotto Jun 17 '17 at 16:23
• 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? $\ \$ – Bill Dubuque Jun 17 '17 at 17:24
• 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 – Esteban Sargiotto Jun 17 '17 at 17:54
• 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. – Bill Dubuque Jun 17 '17 at 18:10

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.

• 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$. – Bernard Jun 17 '17 at 18:44
• @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. – Mastrem Jun 17 '17 at 18:48

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\}.$$