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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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).

Answer 4

$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$