# Tag Info

14

$x=x^3/x^2$, so if $x^3=a^2$ then $x=(a/x)^2$.

6

Hint: You're asking for $2^k|(a+1)(a-1).$ $\gcd(a+1,a-1)$ is at most $2$.

6

Note that $$1000\equiv -1 (mod 13)$$ $$999 998 997. . . 003 002 001=$$ $$1+2(1000)^1+3(1000)^2+...+999(1000)^{998} \equiv$$ $$1(1)+2(-1)+3(1)+4(-1)+....+999(1) =$$ $$=1-2+3-4+...+999=500 \equiv 6 (mod 13)$$

6

Aqua, here it is. As you've obtained, $x\equiv 2\pmod{5}$. Now, $x(x-1)(x+1)=5y^2-9$. Note that, $x+1\equiv 3\pmod{5}$, and is odd. I now claim that, there is a prime $p\mid x(x-1)(x+1)$ such that $p\equiv 2,3\pmod{5}$, and $p\neq 3$. If $x\equiv 1,2\pmod{3}$, then the object $x$ clearly has such a prime divisor (indeed, if all prime divisors of $x$ are of ...

5

Hint: If you compute the remainders of the division of $2^n$ by $7$ when $n=1,2,3,\ldots$, what you get is $2$, $4$, $1$, $2$, $4$, $1$, $2$ … Don't you see a pattern here?

5

In quotient rings of Euclidean domains such as $\,\Bbb Z\,$ and polynomial rings $\,F[x]\,$ we can choose a least element in each class as a canonical rep ("normal form"), then transport the ring operations to these normal elements - just as you do above in the well-known case $\,\Bbb Z_n = \Bbb Z/n =$ integers $\!\bmod n.$ However, this is not possible ...

5

Using division with remainder, if $n=q_kk+r_k$ s.t. $0\leq r_k < k$, then $r_k=n \pmod{k}$. Also $q_k=\left \lfloor \frac{n}{k} \right \rfloor$ and $$r_k=n-k\left \lfloor \frac{n}{k} \right \rfloor$$ Then $$\frac{1}{n^2}\sum_{k=1}^{n}(n \bmod k)= \frac{1}{n^2}\sum_{k=1}^{n}r_k= \frac{1}{n^2}\sum_{k=1}^{n}\left(n-k\left \lfloor \frac{n}{k} \right \rfloor\... 4 We have that 1-(-29)=30 so 5 divides to 1-(-29). That means that -29 \equiv 1 \ (\mbox {mod }5). By transitivity we have that if  3x \equiv -29 \ (\mbox {mod }5) and -29 \equiv 1 \ (\mbox {mod }5) then  3x \equiv 1 \ (\mbox {mod }5). 3 HINT: For m = 11, it obviously does not hold. So you have only 9 numbers to try, namely 2,3,4,5,6,7,8,9,10. 3 We have 323=324-1=18^2-1=17\times 19. So by CRT, it suffices to show x^{144}\equiv 1\pmod{17} and x^{144}\equiv 1\pmod{19} for all x coprime to 17 and 19. Can you finish it from here? 2 Hint: one of 2,5,10 must be a quadratic residue. 2 Euler's theorem asserts that every element a which is coprime to n, i.e. which is a unit mod. n, satisfies \:a^{\varphi(n)}\equiv 1\mod n. This does not mean the order of a is \varphi(n), only that it is a divisor of \varphi(n). Now, let's use the high school factorisation:$$0\equiv 1-a^{\varphi(n)}=(1-a)(1+a+a^2+\dots+a^{\varphi(n)-1}).$$... 2 Obviously a needs to be odd, and by going to -a if necessary we can assume a\equiv 1\pmod 4. Therefore assume a=2^nm+1 with n\ge 2 and m odd. We then have$$ a^2 = 2^{2n}m^2 + 2^{n+1}m + 1 $$In binary, the rightmost set bits are 1 itself and 2^{n+1}. The latter of these does not coincide with any bit of 2^{2n}m^2 because 2n>n+1. That ... 2 It it a very natural thing to do. Consider this real life example: You are in the supermarket buying food. For example you want to have fried rice with lots of vegetables and obviously you also want the dish to look good by having vegetables of different colours. This is your deepest wish right now. Pretend that you are standing in front of the fruits/... 2 Remember n is odd, so writing n=2k+1 gives$$2^{n-3}-1\equiv 2^{2k-2}-1\equiv (2^2)^{k-1}-1\equiv 1-1\equiv 0\pmod{3}$$2 p\neq 3, p\equiv 3\bmod 4. q\equiv p^2+1\pmod{3p} is equivalent to$$q\equiv p^2+1\pmod{3}\hbox{ and }q\equiv p^2+1\pmod{p}$$i.e.$$q\equiv 2\pmod{3}\hbox{ and }q\equiv 1\pmod{p}$$In particular, you have \left(\frac{q}{3}\right)=-1 and \left(\frac{q}{p}\right)=1. Since q divides (12p)^{2019}+1. We have that (12p)^{2019}\equiv -1\bmod{q}... 2  \newcommand{\ord}{\mathop{\rm ord}\nolimits}  As a technical note about notation: (x \ \mathrm{mod}\ m) is an infinite set of integers and sums of infinite sets are more infinite sets. You could unambiguously indicate what you want by$$ \sum_{k=1}^n f(a^k \ \mathrm{mod}\ m) \text{,} $$where f takes a residue class x \ \mathrm{mod}\ m ... 2 Hint: You know (x^n)^2-1\equiv (x^n+1)(x^n-1)\equiv 0. This means that both p and q divide (x^n+1)(x^n-1). Show that neither p nor q divides x^n+1. Actually, the previous argument is unduly complicated. Since Fermat's little theorem implies x^{p-1}\equiv 1\pmod p, you have$$ x^n=(x^{p-1})^{(q-1)/2}\equiv 1^{(q-1)/2}=1\pmod p. $$This means ... 2 This follows from the structure of the group G=\Bbb{Z}_{p^k}^*. More specifically from the fact that G is cyclic of order p^{k-1}(p-1). It is clear that a must be coprime to p, so we can think of a as an element of G. Let m be the order of a in this group. By Lagrange's theorem m\mid p^{k-1}(p-1). On the other hand we know that a^{n-1}\... 2 Hints: By Fermat’s little theorem, since 17 and 19 are prime, x^{16}\equiv1\mod17 and x^{18}\equiv1\mod19. Use the constant case of the Chinese remainder theorem. 2 As 323=17\cdot 19, so x is coprime both to 17 and 19. By lil' Fermat, x has order 16 modulo 17, and 18 modulo 19. Therefore, it has order \operatorname{lcm}(16,18)=144 modulo 323. 2 Sure for d\geq 2. Just pick f(x,y)=x^2-q where q is a quadratic nonresidue mod p, for example, or if p=2 pick f(x,y)=x^2+x+1. Note that an even more trivial example: f(x,y)=1+pg(x,y) with g(x,y)\in\mathbb{Z}[x,y] any degree d polynomial, also give no zeros when reduced mod p. This is essentially the only example for d=1. 1 after the clues that you guys give i have figured out that m =7 and$$11^{2018} \equiv 2 \pmod 7 $$Is that correct? 1 You already got a\equiv 1\bmod 3, which means a\equiv 1,4\hbox{ or }7\bmod 9. We would like to check which of them is the one that works. Now, you can look \mod 9 by using Euler's theorem. Since \gcd(a,9)=1 you can apply Euler's theorem. We have \varphi(9)=6, so$$a^{226}+4a+1=(a^6)^{38}a^{-2}+4a+1\equiv \overline{a}^2+4a+1\mod 9where \... 1 Hint \ 2\mid a,b\,\Rightarrow\ a,b\mid ab/2\,\Rightarrow\, \color{#c00}{{\rm lcm}(a,b)}\mid \color{#0a0}{ab/2} Recall: \ \ \begin{align} x^{\large a}\equiv 1\!\!\pmod{\!p}\\ x^{\large b}\equiv 1\!\!\pmod{\!q}\end{align}\,\Rightarrow\, x^{\large \color{#c00}{{\rm lcm}(a,b)}}\equiv 1\pmod{\!pq},\  so \ x^{\large\color{#0a0}{ab/2}}\equiv 1\pmod{\!pq}\  ... 1 In one hand, since n\geq 3 then 8|2^n, i.e. 2^n\equiv 0\bmod 8. Hence2^n-1\equiv 7\mod 8$$On the other hand, since n is odd, we have 2^n\equiv(-1)^n=-1\bmod 3. Hence, 2^n-1\equiv -2\bmod 3. In particular$$2^n-1\equiv 7\mod 3.$$So, we conclude 2^n-1\equiv 7\mod 24. 1 Hint \,\ 2^{\overbrace{\large 3+2k}^{\LARGE n}}\bmod 24\, =\, 2^{\large 3}(\overbrace{\color{#c00}2^{\large\color{#c00} 2k}\!\bmod 3}^{\large \color{#c00}{2^{\LARGE 2}}\ \equiv\ 1})\, =\, 2^{\large 3}\  We used: \,\ ab\bmod ac\, =\, a(b\bmod c)\,=  mod Distributive Law to factor \,a = 2^{\large 3} out of the mod. 1 x\equiv 2 \pmod{3} is equivalent to say x=2+3k for some k\in \mathbb{Z}. Substitute this into the second congruence and you have$$2(2+3k)\equiv 1 \pmod{5}$$or$$k\equiv 2 \pmod{5}$$Which means k=2+5\ell and that x=2+3(2+5\ell)=8+15\ell for \ell\in \mathbb{Z}. Finally, put this into the last congruence and then$$3(8+15\ell)\equiv 3 \pmod{6}$$... 1 Sometimes some problems are hard to tackle for the whole \mathbb{Z}. So, taking the residue classes helps to simplify our problem and we have a smaller set to start the problem. Moreover, In abstract algebra, there are Zero divisors which needs to be eliminated from the discussion as they make a "non-useful class". So, Quotient removes these kinds of ... 1 Hint: Consider a square-free integer: \;N=p_1p_2\dotsm p_r. By the Chinese Remainder theorem, solving the equation x^2\equiv 1\pmod N is equivalent to solving the set of congruences$$\begin{cases} x^2\equiv 1\pmod{p_1} \\ \quad\enspace\vdots\\x^2\equiv 1\pmod{p_r} \end{cases}\iff \begin{cases} x\equiv\pm 1\pmod{p_1} \\ \quad\,\vdots\\x \equiv \pm1\...

Only top voted, non community-wiki answers of a minimum length are eligible