Does there exist an integer $x$ satisfying the following congruence:  $10x=1\mod 21$  $5x=1\mod 6$  $4x=1\mod 7$  My try:  Using Chinese Remainder Theorem:  $n=n_1*n_2*n_3=21*6*7=882$ . Then consider  $n_1^{'}=42,n_2^{'}=147,n_3^{'}=126$.  Consider $n_1^{'}x \equiv 1\mod n_1$,$n_2^{'}x \equiv 1\mod n_2$,$n_3^{'}x \equiv 1\mod n_3$ .  Substituting we get $42x\equiv 1\mod(21)$,$147x\equiv 1\mod(6)$,$126x\equiv 1\mod(7)$  But  $42x\equiv 1\mod(21)$, is never true as $21*2=42$  Thus no such solution exists. Is this true?
122050
Does there exist an integer $x$ satisfying the following congruences?   $$10x = 1 \pmod {21} \\ 5x = 2 \pmod 6 \\ 4x = 1 \pmod 7$$      I was trying to do this by following way but failed to get an answer:-  At first rewrite the equation as: $$\begin{align}10x = 1 \pmod 3 \tag{1} \\    10x = 1 \pmod 7 \tag{2} \\    5x = 2 \pmod 2 \tag{3} \\   5x = 2 \pmod 3 \tag{4} \\      4x = 1 \pmod 7 \tag{5}\end{align}$$ But equation $(1)$ and $(4)$, and $(2)$ and $(5)$ are same. So it becomes as: $$10x = 1 \pmod 3 \\    10x = 1 \pmod 7 \\ 5x = 2 \pmod 2$$  and now try to solve this by Chinese Remainder Theorem. But the answer does not satisfy. Is my process wrong?
58863
Let $n &gt; 1$ be any positive integer and consider $(\mathbb{Z}/n)^\times$. We want to find all elements $x \in (\mathbb{Z}/n)^\times$ such that $x \equiv x^{-1} \mod n$.  After testing a few different $n$, I am certain that the only elements will be $1$ and $n - 1$. This is certainly true when $n$ is prime. Showing it when $n$ is composite is more difficult:  Assume that $x \equiv x^{-1} \mod n$. Then $x^2 \equiv 1 \mod n$ and so $x^2 - 1 \equiv 0 \mod n$, which implies that $(x - 1)(x + 1) \equiv 0 \mod n$. Now if $n$ is prime, we could just conclude that $n | (x - 1)$ or $n | (x + 1)$. But I am unsure what to do in the case that $n$ is composite.
59847
I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively.  So I start defining  $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, m_2m_3=20,$$$$ m=60$$ All the moduli are pairwise coprime, so by the Euclidean Algorithm $$12x+5y=1\Rightarrow x=-2, y=5.$$ $$15x+4y=1\Rightarrow x=-1, y=4.$$ $$20x+3y=1\Rightarrow x=-1, y=7.$$ Therefor a solution should be  $$20\cdot(-2)\cdot1 +15\cdot (-1)\cdot 2+12\cdot (-1)\cdot 3=-40-30-36=-106$$ But under mod 60, this implies a solutions should be of the form, $60t+14$.  But it is not.  THis is not right.  Why did this technique not work?
105231
What solutions does the equation $4x\equiv2\mod10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax\equiv d\mod n$, where $d=\gcd(a,n)$?  This is the question that appeared in our universities last year paper. But it seems very difficult for me like for first part I am able to solve by simplifications I got $x=5\cdot Z +3$ as solution which makes sense and seems fair but for the second one, I have no idea how can I approach that. Can you please help me out with that one. I tried to simplify that by using Euclidean algorithm but still, I didn't get any idea that what actually the solution will be. My final exam is on 2nd of next month and because of covid I am unable to contact in person for any help. So any help from this site will be appreciated. Thank you for looking at this question!
36462
As the title implies.  I'm proving it by contradiction and I've already ruled out $p \equiv 0$ and $2$ (mod $4$).  I'm having trouble proving that it cannot be $\equiv 3$ (mod $4$). Namely, if $p \equiv 3$ (mod 4), then $m^2 + n^2 \equiv 1$ or $3$ (mod $4$). I know that $m^2 + n^2$ cannot be congruent to $3$ (mod $4$); but what about $1$?  Thank you.
101477
Why does the equation $x^2\equiv2 \pmod 5$ have no solutions?  I did a remainders table and found that $$x^2\equiv0;1;4\pmod 5$$  But is there any way to justify this besides that?  The original equation was $2x^2\equiv9\pmod 5$ but I got it to the form above.
957
Show that    $$1^{p-1} + 2^{p-1} +\ldots + (p-1)^{p-1} \equiv -1 \mod p$$   So, I use Fermat's little theorem, that is if $p$ does not divide $a$, then $a^{p-1}$ is congruent to $1$ (mod $p$). But I'm still confused. If $1^{p-1}$ is congruent to $1$ (mod $p$), $2^{p-1}$ is congruent to $1$ (mod $p$), and $p$ does not divide $p-1$, so $(p-1)^{p-1}$ is congruent to $1$ (mod $p$). How does that equal $-1$ (mod $p$)?
77523
I've been asked to show that:  $n(n+1)(2n+1) \equiv 0 \pmod 6$  I found in a previous question that:  $n(n+1)$ was divisible by $2$ and resulted in an even number e.g  $n(n+1) \equiv 0 \pmod 2$  so I figured I needed to find:  $(2n+1) \equiv 0 \pmod 3$ in order to complete  $n(n+1)(2n+1) \equiv 0 \pmod 6$  but I am unsure on how to find $(2n+1) \equiv 0 \pmod 3$  Is this the right way to find the mod 6 and if so could you tell me how I could find  $(2n+1) \equiv 0 \pmod 3?$
113858
So I'm trying to find a solution for the equation $$(65!)^2\equiv x\:(\text{mod}\: 131)$$ I'm given the hint to use Wilson's Theorem which states, that for a prime $p$ we have $(p-1)!\equiv -1\:(\text{mod}\:p)$.   The only thing I've managed to so far is insert my number in Wilson's Theorem: So I get $(130!)\equiv -1\:(\text{mod}\: 131)$. From here on I have no idea what to do.   Any help would be appreciated. Apologies for any english errors.
105411
I have checked the solution ($x=26$).  Solving modulo $5$ gives  $$1978^{20}\equiv 1978^{2\cdot 10}\equiv 1\pmod{5}$$  Solving modulo $25$ also gives $$1978^{20}\equiv 1\pmod{5}$$  How to evaluate the remainder $x$?
47673
Are there solutions in integers $a,b&gt;1$ to the following simultaneous congruences? $$ a^4\equiv 1 \pmod{b^2} \quad \mathrm{and} \quad b^4\equiv1 \pmod{a^2} $$  A brute-force search didn't turn up any small ones, but I also don't see how to rule them out.
68072
I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google:  .  Anyway, the books lists many assertions without proof, only references which I can't find. One I could not solve for myself said that not all even numbers are values of $\phi(n)$. The sequence of even non-values of $\phi(n)$ starts:  $14, 26, 34, 38, 50, 62,\dots$  After thinking about it for a while, I've made little headway. Looking at 14 specifically, I suppose if such a solution $a$ to $\phi(x)=14$ were to exist, $(a,m_i)=1$ for $1\leq i\leq 14$, for some $m_i\lt a$ and so there must also exist inverses $\overline{a_i}$ such that $\overline{a_i}a\equiv 1 \pmod {m_i}$ for each $i$. I'm looking for some contradiction, possibly of the Chinese Remainder Theorem, to show such $a$ cannot exist.   Is there some way to generalize which values are not taken by $\phi$, or at least explain why this is the case? I was hoping to see why $14$ is the least such integer such that this is true, but values $1$ to $13$ must be indeed taken. I suppose this would also explain why 26 is the next such value that is not taken, while $15$ to $25$ are.
46053
I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + 2),$$ I'm not sure how to solve the $10n^3$ part of the congruence in $\mod 3$. Also, if I have any mistakes please let me know.
3352
I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two:   $13^{100} \bmod 7$ $7^{100} \bmod 13$   I've also heard of this formula:  $$a \equiv b\pmod n \Rightarrow a^k \equiv b^k \pmod n $$  But I don't see how exactly to use that here, because from $13^1 \bmod 7$ I get 6, and $13^2 \bmod 7$ is 1. I'm unclear as to which one to raise to the kth power here (I'm assuming k = 100?)  Any hints or pointers in the right direction would be great.
102472
Question     Numbers $n$ of the form $10^{m}(2^{k}−1)+2^{k-1}−1$, where $m$ is the number of decimal digits of $ 2^{k-1}$. For example:         $k=1$ then $n=10$.   $k=2$ then $n=31$.    $k=3$ then  $n=73$.   $k=4$ then $n=157.$      Conjecture:   the number $(2^k-1)\cdot 10^m+2^{k-1}-1$ where $m$ is the number of decimal digits of $2^{k-1}$ is never prime when it is of the form $7s+6$, that is when it is congruent to $6$ $\pmod 7$. Examples: $n=1023511$ ($k=10$)$\equiv 6 \pmod 7$ and thus it is composite $(1023511=19\times103\times523)$, $n=20471023$ ($k=11$) $\equiv 6 \pmod 7$ and thus it is composite ($20471023=479\times42737)$. With PFGW we arrived to $k=565000$ and all the $n's$ congruent to $6 \pmod 7$ are composite. According to Giovanni Resta's calculations in a post which has been canceled, there should be no probable prime congruent to 6 $\pmod 7$ upto k=800.000. The residue $6$ $\pmod 7$ occurs when either $m=6t+3$ and $k=3l+1$ or $m=6t+4$ and $k=3l+2$ with $k$ and $l$ some non-negative integers, but amazingly when it occurs the number is not prime. Can you find a counter-example or give a proof for the conjecture? Here a link to other interesting questions:  and  For primes of this form see:  The following vector contains all the exponents k&lt;=366800 leading to a prime  $[2, 3, 4, 7, 8, 12, 19, 22, 36, 46, 51, 67, 79, 215, 359, 394, 451, 1323, 2131, 3336, 3371, 6231, 19179, 39699, 51456, 56238, 69660, 75894, 79798, 92020, 174968, 176006, 181015, 285019, 331259, 360787, 366770]$  Exponent $541456$ leads to another probable prime with residue 5 mod 7 and 325990 digits, but it need not be the next in increasing order.  Remark: we found five-in-a-row probable primes with res 5 mod 7. Probable primes with residue 5 are now twice frequent than expected. Exponents of these primes seem to be NOT random at all. Another thing I noticed, i don't know if it has some importance: the exponents leading to a probable prime $215, 69660, 92020, 541456$ are multiples of $43$. I noticed that $\frac{215}{41}, \frac{69660}{41}, \frac{92020}{41}, \frac{541456}{41}$ all have a periodic decimal expansion equal to $\overline{24390}=29^3+1$. This is equivalent to say that when k is a multiple of 43 and the number $10^{m}(2^{k}−1)+2^{k-1}−1$ is prime, then k is of the form $41s+r$ where r is a number in the set (1,10,16,18,37). Is there some mathematical reason for that?
19737
I'm trying to teach myself some number theory. In my textbook, this proof is given:  Example (2.3.1) Show that an integer is divisible by 3 if and only if the sum of its digits is a multiple of 3. Let $n=a_0a_1\ldots a_k$ be the decimal representation of an integer $n$. Thus $n=a_k+a_{k-1}10+a_{k-2}10^2+\cdots+a_010^k$ where $0\le a_i&lt;10$ The key observation is that $10\equiv1\pmod3$, i.e., $[10]=[1]$. Hence $[10^i]=[10]^i=[1]$, i.e., $10^i\equiv1\pmod 3$. The assertion is an immediate consequence of this congruence.  I don't understand the last statement. Why does it follow from that congruence?
12212
The question is     Suppose p is a prime number and p does not divide a. Prove that the congruence $ax \equiv 1 \mod p$ has a solution   (Without using Fermat's Theorem), I can intuitively tell this is true because since $p$ is prime, every $x &lt; p$ is co-prime to it, thus $$x \mod p$$  Will produce a unique integer for each $x \in \{0, 1, 2, .... p-1\}$, before it cycles over again at $p$. Clearly, some $x$ must have that $x \mod p = 1$. However, I don't know how to prove this for $ax$, mainly because I can't prove the ramifications it can have on the mod cycle. What I do know is that if for some $x$, we have: $$ax \equiv ay \mod p$$ Then since $p$ doesn't divide $a$ (by question assumption), it must divides $x - y$, implying that the solution for $ax \equiv 1 \mod p$ only depends on $x$, however, I don't know how to show this rigorously. Could anyone enlighten me?