# Let $S = \{n\in\mathbb{N}\mid 133 \text{ divides } 3^n + 1\}$. Find three elements of S.

Question:
Let $S = \{n\in\mathbb{N}\mid 133 \;\text{divides} \; 3^n + 1\}$
$a)$ Find three different elements of $S$.
$b)$ Prove that $S$ is an infinite set.

My intuition is find the prime factors of $133$, which is $7$ and $19$. However, I then have no clue what to do? Any Hints? Many thanks, D.

• Find $A = \{n : 19 \mid 3^n + 1\}$ and $B = \{n : 7 \mid 3^n+1\}$. – Daniel Fischer Feb 12 '16 at 13:15
• @DanielfFischer do you mean to find the intersection. But that would take a lot of time right just for the calculation – Sebastian Y. Feb 12 '16 at 13:16
• No, it is easier to break the problem up this way. @DeanY – Thomas Andrews Feb 12 '16 at 13:16
• It wouldn't. Fermat can help you quickly determine $A$ and $B$. – Daniel Fischer Feb 12 '16 at 13:17
• oh right, thanks, but any tips on part b) – Sebastian Y. Feb 12 '16 at 13:17

As an answer to part b, if there are 3 different positive integers $(a,b,c)$ that satisfy the condition, then so do $a+b+c$. Because

$$3^a\equiv -1 \pmod {133}\\3^b\equiv -1 \pmod {133}\\3^c\equiv -1 \pmod {133}$$

and by multiplication property of modular operation we have

$$3^{a+b+c}\equiv (-1).(-1).(-1)\equiv -1 \pmod {133}$$ , $a+b+c\ne\ a,b, c$

Therefore, we have a new positive integer and if the new number is called $d$, then the same process can be done, using a new triple this time ($a,b,d$ for example), to find a new number that would be greater than all of them.

Now, to make a contradiction, let's assume that the set of all such integers $S$ is a limited set. First we need to sort them in ascending order in order to find three elements that are greater than the others. Name them $a,b,c$. By doing the above mentioned process, we find an element $d$ that is strictly greater than $a,b,c$. So, $d$ is not in the set $S$ and this is a contradiction to the fact that $d$ actually satisfies the condition.

• If course, you don't need three to get that. If you have $3^{a}\equiv -1\pmod{133}$ then $3^{3a}\equiv -1\pmod{133}$. No reason to use different $a,b,c$ to show there are infinitely many. – Thomas Andrews Feb 12 '16 at 14:16
• yes. you are right. my mind was conditioned with the first part of the question. – Med Feb 12 '16 at 14:30

For (b), it is clear that if $S$ is not empty then it is infinite because $n_0+\phi(133)\mathbb Z \subseteq S$ if $n_0 \in S$.

Use Euler's theorem. You know that $133 = 7 \cdot 19$, so $\phi(133) = 133 (1 - 1 / 3) \cdot (1 - 1 / 19) = 108$.

You want $n$ such that $3^n + 1 \equiv 0 \pmod{133}$, which (by squaring) is $3^{2 n} \equiv 1 \pmod{133}$. Now $\gcd(3, 133) = 1$, so by Euler's theorem $3^{108} \equiv 1 \pmod{133}$. All you need is $n$ such that $3^n \equiv -1 \pmod{133}$, then $S = \{ n + 108 k \mid k \in \mathbb{N}_0 \}$.

We know is that $3^{108} \equiv 1 \pmod{133}$, so candidates for $n$ are the divisors of $108/2 = 2 \cdot 3^3$, which are $1, 2, 3, 6, 9, 18, 27, 54$. We can eliminate $1, 2, 3$ directly. $3^6 \equiv 64$, and $3^9 \equiv -1 \pmod{133}$. Your set is $S = \{ 3 + 108 k \mid k \in \mathbb{N}_0 \}$, i e., $S = \{9, 117, 225 \dotsc \}$

(Most calcultions checked with trusty bc(1) under Fedora).

• Once we know $3^9 = -1$ we know $3^{18} = 1$ so $3^{9 + k 18} = -1$ S={9, 27, 45, 63, 81, 99, 117, ...} I just found 5 times as many as you did :) ! – fleablood Feb 13 '16 at 3:10
• I was asked for 3. But point taken. – vonbrand Feb 13 '16 at 12:19

$3^3\equiv-1\pmod7\implies3^{3(2m+1)}\equiv-1$ for some integer $m$

Now $3^3\equiv8\pmod{19},3^6\equiv8^2\equiv7\implies3^9=3^6\cdot3^3\equiv7\cdot8\equiv-1$

$\implies3^{\text{lcm}(3,9)}\equiv-1\pmod{\text{lcm}(7,19)}$

$\implies3^9\equiv-1\pmod{133}\implies3^{9(2n+1)}\equiv-1$ for some integer $n$

$\implies3^{18}=(3^9)^2\equiv(-1)^2\pmod{133}\equiv1$

So, $S = \{ 9 + 18 k \mid k \in \mathbb{N}_0 \}$

Alternatively we need, $6m+3=18n+9\iff m=3n+1$