4
$\begingroup$

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.

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

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Feb 12 '16 at 14:16
  • $\begingroup$ yes. you are right. my mind was conditioned with the first part of the question. $\endgroup$ – Med Feb 12 '16 at 14:30
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 :) ! $\endgroup$ – fleablood Feb 13 '16 at 3:10
  • $\begingroup$ I was asked for 3. But point taken. $\endgroup$ – vonbrand Feb 13 '16 at 12:19
0
$\begingroup$

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

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