+0  
 
+2
1883
3
avatar+488 

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

 Jan 13, 2018
 #1
avatar
+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].

 Jan 13, 2018
edited by Guest  Jan 13, 2018
 #2
avatar+488 
+2

Thanks! but that is incorrect, you forgot 1

RektTheNoob  Jan 13, 2018
edited by RektTheNoob  Jan 13, 2018
 #3
avatar+26364 
+2

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

 

laugh

 Jan 15, 2018

3 Online Users

avatar
avatar