+489 Determine the number of positive integers a less than 12 such that the congruence \(ax\equiv 1\pmod{12}\) has a solution in x.
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].
+26393 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
