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**+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

#3**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