+0

0
294
2
+283

1. Find all residues $a$ such that $a$ is its own inverse modulo $317$.
(Your answer should be a list of integers greater than 0 and less than $317$ separated by commas.)

2. The inverse of $a$ modulo 39 is $b$. What is the inverse of $4a$ modulo 39 in terms of $b$?
Give your answer as an expression in terms of $b$.

3. Let $x$ and $y$ be integers satisfying $41x+53y=12$. Find the residue of $x$ modulo 53.

4. Find the sum of all positive rational numbers that are less than 5, and that have a denominator of 30 when written in lowest terms.

Jul 30, 2018

#1
+22869
+1

3.

Let x and y be integers satisfying 41x+53y=12.
Find the residue of x modulo 53.

$$\small{ \begin{array}{|rcl|cl|} \hline 41x+53y &=& 12 \quad |\quad \cdot (-1) \\ -41x-53y &=& -12 \\ -41x &=& -12 +53y \\ \\ \hline \\ -41x &\equiv & -12 \pmod{53} \quad |\quad : (-41) \\\\ x &\equiv & \dfrac{-12}{-41} \pmod{53} \\\\ x &\equiv & \dfrac{12}{41} \pmod{53} \\\\ x &\equiv & 12\cdot 41^{-1} \pmod{53} && 41^{-1} \pmod{53} \quad | \quad \gcd(41,53)=1 \\\\ && &\equiv & 41^{\phi(53)-1} \quad | \quad \phi(53)= 52 \\\\ && &\equiv & 41^{52-1} \pmod{53} \\\\ && &\equiv & 41^{51} \pmod{53} \\\\ && &\equiv & 22 \pmod{53} \\\\ x &\equiv & 12\cdot 22 \pmod{53} \\\\ x &\equiv & 264 \pmod{53} \\\\ \mathbf{x} & \mathbf{\equiv} & \mathbf{52 \pmod{53}} \\ \hline \end{array} }$$

Proof:

$$\begin{array}{|rclr|} \hline 41x+53y &=& 12 \quad & | \quad \pmod{53} \\ 41x \pmod{53}+53y \pmod{53} &=& 12 \pmod{53} \quad & | \quad x \equiv 52 \pmod{53} \\ 41\cdot52 \pmod{53}+\underbrace{53y}_{\equiv 0\pmod{53} } \pmod{53} &=& 12 \pmod{53} \\ 41\cdot52 \pmod{53}+0 &=& 12 \pmod{53} \\ 2132 \pmod{53} &=& 12 \pmod{53} \\ 12 \pmod{53} &=& 12 \pmod{53}\ \checkmark\\ \hline \end{array}$$

Jul 31, 2018
#2
+22869
0

2.
The inverse of a modulo 39 is b.
What is the inverse of 4a modulo 39 in terms of b?
$$\begin{array}{|rcl|cl|} \hline 4a(4a)^{-1} &\equiv & 1 \pmod{39} \quad |\quad : (4a) \\\\ (4a)^{-1} &\equiv & \dfrac{1}{4a} \pmod{39} \\\\ (4a)^{-1} &\equiv & 4^{-1}a^{-1} \pmod{39} \quad | \quad a^{-1} = b \\\\ (4a)^{-1} &\equiv & 4^{-1} b \pmod{39} && 4^{-1} \pmod{39} \quad | \quad \gcd(4,39)=1 \\\\ && &\equiv & 4^{\phi(39)-1} \quad | \quad \phi(39)= 24 \\\\ && &\equiv & 4^{24-1} \pmod{39} \\\\ && &\equiv & 4^{23} \pmod{39} \\\\ && &\equiv & 10 \pmod{39} \\\\ \mathbf{(4a)^{-1} } & \mathbf{\equiv} & \mathbf{10 b \pmod{39} } \\ \hline \end{array}$$