<jupyter_start><jupyter_text>Can we solve the following?  1. $$3x \equiv 6 \pmod{9}$$ 1. $$3x \equiv 5 \pmod{9}$$<jupyter_code>solve_mod(3*x==6, 9,x) # There are more than one solution!!!
solve_mod(3*x==5, 9,x) # There is no solution<jupyter_output><empty_output><jupyter_text>For the first one, It seems like the solution can be given by $$ x \equiv 2 \pmod{3} $$  For the second one,Assume there is a solution, then \begin{align*}3x & \equiv5\pmod{9}\\9x & \equiv15\pmod{9}\\0 & \equiv6\pmod{9}\end{align*}The last line is impossible. Contradiction.  Multiplicative inverse of $a$ under mod $m$If we can find a solution to $$ax + my = 1$$, we know the inverse of $a$ is given by $x$.  Want to solve $$ 3x \equiv 1 \pmod{7} $$  Solve 3x + 7y = 1<jupyter_code>inverse_mod(3,7) # Inverse of 3 under mod 7<jupyter_output><empty_output><jupyter_text>Investigation<jupyter_code>xgcd(3,7)  #  3(-2) + 7(1) = 1<jupyter_output><empty_output><jupyter_text>\begin{align*}3\left(-2\right)+7\left(1\right) & =1\\3\left(-2\right)+0 & \equiv1\pmod{7}\\3\left(-2\right) & \equiv1\pmod{7}\\3\left(5\right) & \equiv1\pmod{7}\end{align*}  ResultMultiplicate inverse of $a$ exists  under mod $m$ if and only if $\gcd(a,m)=1$In such case, we can find the inverse by Extended Euclidean Algorithm.<jupyter_code>inverse_mod(3,9)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16841317365269462, 'fraction_numerical': 0.048652694610778445, 'mean_word_length': 5.049773755656108, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '612935', 'license': 'MIT', 'n_tokens_mistral': 562, 'n_tokens_neox': 520, 'n_words': 136, 'path': '20210417/3 - Existence of multiplication inverse.ipynb', 'repo_name': 'izayoi-ami/2021-hkage-sage-programming', 'size': '1336'}