1

I was solving a math problem when I came across this Question:

When is $17 \mid 77a+1$ With $a\in \mathbb N^*$

It’s easy to see that there’s infinitely many of values of $a$, you can’t try a little bit with this but you will end up with these values : $$a\in \{15,32,49,66,...\}=A$$ In this set any number it’s equal to the previous one $+17$ . I’ve found a relation with this set and the set contains all numbers divisible by $17$, let’s call it $D_{17}$ $$D_{17} =\{17,34,51,68,...\}$$ You can see that if $n \in D_{17} \iff n-2\in A$ And if $n\in A \iff n+2 \in D_{17}$.

My question is why $2$ appeared here, does there exist an equation that when we solve it we will get this $2$?

Bernard
  • 175,478
PNT
  • 4,164
  • Not following. The solution to $77a\equiv -1 \pmod {17}$ is $a\equiv 15\pmod {17}$. Is that what you are asking? – lulu Feb 14 '21 at 13:33
  • 1
    To solve it mentally, note that $77\equiv 9\pmod {17}$ and that the inverse of $9\pmod {17}$ is clearly $2$. ( Is that the $2$ you are asking about?). It follows at once that the solution to $77a\equiv -1$ is $a\equiv -2\equiv 15$ (all congruences $\pmod {17}$). – lulu Feb 14 '21 at 13:36
  • Hang on i don’t know how to solve linear congruence . – PNT Feb 14 '21 at 13:38
  • Ok...my second comment shows you how to solve this one in particular, Alternatively, with numbers as small as $17$, trial and error is an easy way to solve them. Nothing wrong with doing it that way, though of course it's a terrible method for dealing with very large numbers. – lulu Feb 14 '21 at 13:40
  • For a general technique for this class of problem, look up "Euclid's algorithm". – aschepler Feb 14 '21 at 14:15
  • Where should I use it in this problem ?-@aschepler – PNT Feb 14 '21 at 14:54
  • $17 \mid 77a+1$ if and only if there is an integer $k$ where $77a + 17k = -1$. – aschepler Feb 14 '21 at 16:01

2 Answers2

2

$$77a+1\equiv 17 \bmod 17$$ $$77a\equiv -1 \bmod 17$$ $$9a\equiv -1 \bmod 17$$ The modular inverse of $9\bmod 17$ is $2$ therefore $$a\equiv -2 \bmod 17$$ that is $$a=17n-2;\;\forall n\in\mathbb{N^*}$$

Raffaele
  • 26,371
  • So there’s no way you can get an answer without use modular arithmetic ? – PNT Feb 14 '21 at 18:37
  • @Yassir Yes, there is. When you wrote $$a\in {15,32,49,66,...}=A$$ $A$ is the set of multiple of $17$ less $2$ that is the same as $a=17n-2$ – Raffaele Feb 14 '21 at 18:43
0

Divisibility by $17$.- A number $n$ is divisible by $17$ if, subtracting from the number without the units digit the units digit multiplied by $5$, the result is equal to a multiple of $17$.

When $17|77a+1?$. You have $77a+1=(4\cdot17+9)a+1$ so you need $17|9a+1$

Consider $9a+1\equiv\alpha_1\pmod{10}$ According with the criterium above we make

$(9a+1-\alpha_1)-5\alpha_1\equiv0\pmod{17}$ and iterating the procedure until the congruence could be clearly seen to be true or false, we have the answer.

Piquito
  • 29,594