Find all the positive integers such that $n+7$ is divisible by $3n-1$

Question

I am trying to solve some practice problems and found this one which I can't solve:

Find all the positive integers such that $n+7$ is divisible by $3n-1$

So far I have tried using the usual properties such as $a|b$ then $a|bc$ ; $a|b$ and $a|c$ then $a|bx+cy$ ; etc but I can't get to anything useful. Just by looking, apparently the answers should be 1 and 4 but that's all I can get.

Here on mathstack I was able to find some similar ones but that only have a number (i.e: 7|[whatever expression] but I don't see how to relate them to mine) If possible, please avoid using congruence for the solution.

Answer 1

Since $3n-1$ divides it self and $3\cdot (n+7)$ we have $$3n-1\mid 3(n+7)-(3n-1)$$ so $3n-1\mid 22$ which means $$3n-1\in\{1,2,11,22,-1,-2,-11,-22\}$$

so $$3n\in\{2,3,12,23,0,-1,-10,-21\}$$

so $$3n\in\{3,12,0,-21\}\implies n\in\{1,4,0,-7\}$$

so we found all integer solutions.

Answer 2

Note that if $a$ is divisible by $b$, then $|b| \leq |a|$. So, a necessary (but not sufficient) condition is $|3n - 1| \leq |n + 7|$. Going the lazy route, we can plot the graphs $y = |3x - 1|$ in red and $y = |x + 7|$ in blue and see:

We see that $-\frac{3}{2} \leq n \leq 4$, so we only have to consider the cases $n \in \{-1, 0, 1, 2, 3, 4\}$.

Answer 3

Hint:$$22=3(n+7)-(3n-1)$$ Why does $3n-1$ divide $22$? How did we reach this number? List all the factors of $22$ and finish it off.

Answer 4

While there are definitely approaches with heavier artillery that will work on more broad versions of this problem, sometimes recognising that you get away with using a peashooter is an important skill as well.

First note that for both positive $a \vert b$ means $a \leq b$, so $3n-1 \leq n+7 \implies n\leq 4$ and there are only four cases to check.

For $n=1$, we get $\frac{8}{2}=4$.

For $n=2$, we get $\frac{9}{5}=1.8$.

For $n=3$, we get $\frac{10}{8}=1.25$.

For $n=4$, we get $\frac{11}{11}=1$.

If you also want to check zero, we get $\frac{7}{-1}=-7$. But if you allow negative number inputs, there is more required.

Answer 5

Let's start with the basics. If $n+7$ is to be divisible by $3n-1$, then $n+7\ge 3n-1$, which of course means $8\ge 2n \Longrightarrow n\le 4$. Because the question specifies that $n$ be a positive integer, that leaves you with four cases to check: $n \in \{1,2,3,4\}$.

Addendum:

just for fun, let's work out every possible integer value for $n$, not just the positive ones. To do this we will use a modified form of the above argument.

If $n+7$ is divisible by $3n-1$, then $|3n-1|\le |n+7|$. By the definition of absolute value, $|3n-1| = 3n-1$ when $n\ge1/3$ and when $n\lt1/3$, it is equal to $1-3n$. On the other hand, $|n+7| = n+7$ when $n\ge-7$. These facts combine to yield the following set of inequalities over a set of intervals, and we will use these to bound the possibilities for $n$.

Case 1: $1/3 \le n$

I already solved this in my original answer, but it's worth going over again. If $n\ge1/3$, then $|3n-1|\le |n+7| \Longrightarrow 3n-1\le n+7 \Longrightarrow n\le 4$.

Case 2: $-7\le n \lt 1/3$

In this case, the inequality $|3n-1| \le |n+7|$ becomes $1-3n \le n+7$. Solve this for $n$ and you get $-6\le 4n$, or $n\ge -3/2$. Since $n$ has to be an integer, that leaves us with two new possibilities to check: $n=-1$ and $n=0$. If $n=-1$, then $n+7 = 6$ and $3n-1 = -4$. $6$ is not divisible by $-4$, so $n=-1$ is a bust. However, $n=0$ does work (try it for yourself!)

Case 3: $n\lt-7$

When $n\lt-7$, $|3n-1|=1-3n$ and $|n+7| = -n-7$, so $|3n-1|\le|n+7| \Longrightarrow 1-3n \le -n-7$. This implies that $8\le2n$, or that $n\ge 4$. However, $n$ cannot simultaneously be less than $-7$ and greater than $4$; this is a contradiction. Therefore there are no integers $n$ less than $-7$ such that $3n-1$ divides $n+7$.

In full: if $n$ is to be any integer, not just a positive one, such that $3n-1|n+7$, then $n\in \{0,1,4\}$

Answer 6

Since $(n+7)$ is divisible by $(3n−1)$, we have

$n+7=k(3n-1)$

$n+7=3nk-k$,

$3nk-n-k-7=0$.

This is a quadratic Diophantine equation. To find the solution, rewrite it into the form of

$(3n-1)(3k-1)=22$

where $22$ can be factorized as the product of $2$ and $11$, which yields two sets of solutions of $(n,k)$ with positive $n$, that is, $(n_1,k_1)=(1,4)$ and $(n_2,k_2)=(4,1)$.

Answer 7

Though you prefer to avoid congruences it is worth emphasizing how they simplify problems like this. Here it allows us to translate divisibility by $\,3n\!-\!1\,$ into arithmetic $\!\bmod 3n\!-\!1\,$ where $\,3n\equiv 1\,$ so $\,n\equiv \frac{1}3$ and now we can use well-known algebra as below

$$\!\bmod\,\color{#c00}{3n}\!-1\!:\ \ \dfrac{1}{\color{#c00}3}\equiv {\color{#c00}n\equiv -7}\!\! \overset{\times\ 3\!\!}\iff 1\equiv -21\iff 3n\!-\!1\mid 22\qquad\qquad$$

Similarly $\,3n\!-\!1\mid f(n)\iff f(1/3)\equiv 0\pmod{3n\!-\!1}\,$ for any polynomial with integers coef's, e.g. here, and we can do this arithmetic fraction-free by scaling $f(1/3)$ by $3^k$ for $\,k=\deg(f),\,$ e.g. here. Generally this is simpler and more (arithmetically) intuitive than alternative approaches (e.g. eliminating $\,n).$

Remark $\ n\equiv 3^{-1}\pmod{\!3n\!-\!1}$ is a special Easy Inverse optimization of the Extended Euclidean Algorithm.