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

+2
182
3
+376

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
+376
+3

Thanks! but that is incorrect, you forgot 1

RektTheNoob  Jan 13, 2018
edited by RektTheNoob  Jan 13, 2018
#3
+19376
+1

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