+0

# Determine the number of positive integers $a$ less than $12$ such that the congruence $ax\equiv 1\pmod{12}$ has a solution in $x$.

+1
47
3
+241

Determine the number of positive integers a less than 12 such that the congruence $$ax\equiv 1\pmod{12}$$ has a solution in x.

RektTheNoob  Jan 13, 2018
Sort:

#1
+3

a=1 and x=1

a=5 and x=5

a=7 and x=7

a=11 and x=11

These are solutions for "a" < 12.

You are right. Sorry about that. [Edited].

Guest Jan 13, 2018
edited by Guest  Jan 13, 2018
#2
+241
+1

Thanks! but that is incorrect, you forgot 1

RektTheNoob  Jan 13, 2018
edited by RektTheNoob  Jan 13, 2018
#3
+18827
0

Determine the number of positive integers a less than 12 such that the congruence

$$ax\equiv 1\pmod{12}$$

has a solution in x.

$$\begin{array}{ll} & ax \equiv 1\pmod{12} \\ \text{or} \\ & ax-1 = y\cdot 12 \\ \text{or} \\ & \mathbf{ax -12y = 1} \\ \end{array}$$

$$\begin{array}{|lll|} \hline \text{The linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers.}\\ \text{The solutions are described by the following theorem:}\\ \text{This Diophantine equation has a solution (where x and y are integers)} \\ \text{if and only if c is a multiple of the greatest common divisor of a and b.} \\ \hline \end{array}$$

Let c = 1

$$ax + by = 1$$

Let b = -12

$$ax-12y = 1$$

There is a solution, if c=1 is a multiple of the gcd(a,-12).   gcd = greatest common divisor

Or gcd(a,-12) | 1,

$$\Rightarrow$$ gcd(a,-12) = 1, because 1 is the only divider of 1!

$$\begin{array}{|r|c|} \hline a & gcd ( a,-12)=1 \ ? \\ \hline {\color{red}1} & {\color{red}1}\\ 2 & 2\\ 3 & 3\\ 4 & 4\\ {\color{red}5} & {\color{red}1}\\ 6 & 6\\ {\color{red}7} & {\color{red}1}\\ 8 & 4\\ 9 & 3\\ 10 & 2 \\ {\color{red}11} & {\color{red}1} \\ \hline \end{array}$$

Number of positive integers a less than 12 such that the congruence
$$ax\equiv 1\pmod{12}$$

are 1, 5, 7, 11

heureka  Jan 15, 2018

### 24 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details