+0  
 
+2
357
3
avatar+408 

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
 #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].

Guest Jan 13, 2018
edited by Guest  Jan 13, 2018
 #2
avatar+408 
+3

Thanks! but that is incorrect, you forgot 1

RektTheNoob  Jan 13, 2018
edited by RektTheNoob  Jan 13, 2018
 #3
avatar+20164 
+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

 

laugh

heureka  Jan 15, 2018

36 Online Users

avatar
avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.