New answers tagged

1 vote
Accepted

Prove that any automorphism $\phi \in Aut(\mathbb{Z}_n)$ is determined by $\phi([1])$ and that $\phi([1])$ must be a generator for $\mathbb{Z}_n$

Since every $k\in\Bbb Z_n$ is $1^k$ (multiplicative notation), a homomorphism of a cyclic group is completely determined by what it does to any generator. And the homomorphism $\phi$ is bijective ...
user avatar
  • 583
0 votes

Prove that any automorphism $\phi \in Aut(\mathbb{Z}_n)$ is determined by $\phi([1])$ and that $\phi([1])$ must be a generator for $\mathbb{Z}_n$

You just need to prove that $o(\phi(1)) =n$. Which is trivial since $$\phi(1)^n=\phi(1^n) =\phi(n) =\phi(0) =0$$
user avatar
2 votes

Prove for any $[a] \in \mathbb{Z}^\times_n$ multiplication by $[a]$ defines an automorphism $\alpha_{[a]}: \mathbb{Z}_n \to \mathbb{Z}_n$

I would suggest that you don't bother with the specific case of $\mathbb Z_n$. Just prove that for any ring $(R, + , \cdot)$ and $a \in R$ the map $$\varphi_a: x \mapsto ax$$ is a homomorphism of the ...
user avatar
1 vote
Accepted

Prove for any $[a] \in \mathbb{Z}^\times_n$ multiplication by $[a]$ defines an automorphism $\alpha_{[a]}: \mathbb{Z}_n \to \mathbb{Z}_n$

Fix $[a]\in\Bbb Z_n^\times$. You need to show the homomorphism property $$\alpha_{[a]}([k]+[l])=\alpha_{[a]}([k])+\alpha_{[a]}([l])$$ for all $[k],[l]\in\Bbb Z_n$, together with either surjectivity or ...
user avatar
  • 38.7k
2 votes

How to find the last two digits of $2011^{2011}$

SOLUTION $1$ : $2011\equiv 11 \mod (100) $ $2011^2\equiv 11^2 \equiv 21 \mod (100) $ $2011^3\equiv 11^3 \equiv 31 \mod (100) $ $2011^4\equiv 11^4 \equiv 41 \mod (100) $ ...................................
user avatar
  • 4,795
2 votes

Is it possible to generalize this equation more?

This is very nice. It relies to the Tarry-Escott problem, on which there is a vast literature going back more than 100 years. I do not know how much you know of this. I suggest you consult Dickson, ...
user avatar
0 votes

Let $n$ be a positive integer. Show that $n\phi(n)=\phi(n^2).$

Since everything that could have been said, has already been said, let me add those probabilistic intuitions involving $\varphi$ function (because I like them)- Note that if $a$ is coprime to $n^2$, ...
user avatar
  • 5,746
0 votes
Accepted

Luhn algorithm for odd and even card numbers?

For odd placed digits going back from the check digit, you have the following mapping: 0 2 4 6 8 1 3 5 7 9 Then add all digits, including the check digit it should form a multiple of ten So the ...
user avatar
3 votes

Proof for a prime-generating sequence

$$n+2=6k+1$$ by Wilson's theorem $$(n+1)!\equiv -1\pmod {n+2}$$ it follows that $$n!\equiv 1\pmod{n+2}$$ and that $$(n-1)!\equiv -(2^{-1})\equiv 3k\pmod {n+2}$$ and $$-n\equiv 2\pmod {n+2}$$ so ...
user avatar
2 votes
Accepted

Given $245^2\equiv 1\pmod{2501}$. Find $x,y$ such that $x\cdot y=2501$.

Note that the factorization of $a^2-1$ is $(a-1)(a+1)$. So, \begin{align*}245^2-1^2 &\equiv 0 \mod 2501 \\ (245-1)(245+1) & \equiv 0 \mod 2501 \\ 244\cdot 246 &\equiv 0 \mod 2501.\end{...
user avatar
  • 152
5 votes
Accepted

Solutions to the equation $x^y \equiv y^x$ in $\mathbb Z / p \mathbb Z$, $p$ prime.

This is more complicated than it looks because solutions to $x^y\equiv y^x\bmod p$ (with $p$ prime) are actually not defined $\bmod p$. They are defined $\bmod p(p-1)$ because the power varies with ...
user avatar
  • 29.8k
1 vote
Accepted

Show that $\Bbb Z_{12}/\langle[3]_{12}\rangle \cong \Bbb Z_p$ for some $p \in \Bbb N$.

The order of $H:=\langle [3]_{12}\rangle$ is four; this follows from $H$ being cyclic (as $G:=\Bbb Z_{12}$ is cyclic) and $$\begin{align} 0[3]_{12}&=[0]_{12}, \\ 1[3]_{12}&=[3]_{12},\\ 2[3]_{...
user avatar
  • 38.7k
0 votes

Express sum of $(a \cdot b) \bmod n$ as regular matrix product

$\def\tmod{~\mathrm{mod}~}$What you can do is us use $f=g:x\mapsto x\tmod n$. Then $g$ maps the input in to some range like $[0,n-1]$ or $[-n/2, n/2-1]$. The former is sometimes called unsigned ...
user avatar
0 votes

What is the proof for this question regarding subtraction in modular arithmetic?

A number that is 1 mod 4 but not 1 mod 8 can be represented as $8k+5$. A number that is 1 mod 8 can be represented as $8m+1$. Their difference is $8(k-m)+4$ which is clearly divisible by 4 but leaves ...
user avatar
0 votes

What is the proof for this question regarding subtraction in modular arithmetic?

Following the hint given by @peter phipps in the comment section, I will attempt to answer the question. @peter phipps has suggested that I reduce category A to modulo 8 which I will do here. I have ...
user avatar
0 votes

What is the proof for this question regarding subtraction in modular arithmetic?

To prove this, we can use the fact that if an integer $a \equiv b \mod n$, there exists another integer $k$ such that $a = b + nk$.
user avatar
0 votes

Coprime with $n$ and their modular inverses in $\Bbb Z_n$

First,your set P must contain all number that coprime to n in$\mathbb{Z} _n$(otherwise you can't proof q is contained in P from q is coprime to n) if $\left( a,n \right) =1$,we konw that $a^{\varphi \...
user avatar
0 votes

Coprime with $n$ and their modular inverses in $\Bbb Z_n$

The set $P$ is a group under multiplication (with reduction modulo $n$). If $G$ is a group, then the map $g\mapsto g^{-1}$ is inverse of itself, so it is a bijection.
user avatar
  • 228k
0 votes

Coprime with $n$ and their modular inverses in $\Bbb Z_n$

If $q p \equiv 1 \pmod n$ then $qp =1+nk$, so $qp-nk=1$. But $\gcd(q,n)$ divides every lineal combination of $q$ and $n$, so $\gcd(q,n) | qp-nk=1 $.
user avatar
  • 11.8k
0 votes

If $n \mid a^n - 1$, prove $ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ are distinct $ \bmod n $.

Probably the same as the previous answers, but written in an understandable form for the small reader. Let $a\in \mathbb N$ and assume the result true by induction up to rank n = K (it is clearly for $...
user avatar
  • 1,621
0 votes
Accepted

Show $2\mid (n^7 -n), \forall n \in\mathbb{N}$.

$n^7-n = n(n^6-1) = n(n^3-1)(n^3+1)=n(n-1)(n^2+n+1)(n^3+1)$. Observe the product consists of $2$ consecutive integers $n,n-1$ hence divisible by $2$.
user avatar
  • 3,379
2 votes

Show $2\mid (n^7 -n), \forall n \in\mathbb{N}$.

If $n$ is odd then $n^7$ must be odd, so $n^7-n$ must be even. If $n$ is even then $n^7$ is even, so $n^7-n$ must be even.
user avatar
  • 6,090
0 votes
Accepted

Suppose $a,b,c\in\mathbb{Z}$. Prove by contradiction that if $a^{2}+b^{2}=c^{2}$, then $a$ or $b$ is even.

Very very short solution: a and b are odd so $$a^2\equiv b^2\equiv 1\bmod 4$$ so $$a^2+b^2=c^2\equiv 1+1\equiv 2\bmod 4$$ which is not possible as squares can only be $\equiv 0,1\bmod 4.$ ...
user avatar
3 votes
Accepted

Let $n=4\cdot p^t+1.$ Is $r_k=4$ for some $1\le k<n$ for an arbitrary prime $p\ge 5$ and integer $t\ge1$

Your conjecture is true Any time one sees recurrence sequences like $r_0=4,r_{k+1}=r_{k}^2-2$, along with something to do with primality, the first thing one should do is think that the recurrence ...
user avatar
  • 1,637
1 vote

Let $n=4\cdot p^t+1.$ Is $r_k=4$ for some $1\le k<n$ for an arbitrary prime $p\ge 5$ and integer $t\ge1$

I can't seem to find a solution using only elementary number theory. From what I did find, it's obvious that we need $$r_{k-1}^2-2\equiv 4 \text{ mod } n$$ $$r_{k-1}^2\equiv 6 \text{ mod } n$$ By the ...
user avatar
  • 532
1 vote

Can someone explain these groups of linear patterns in the dropping times of Collatz Sequences? Could this lead to a proof?

This is an interesting approach to the problem, which has been investigated to some extent, but you might have some novel insights. I'm going to translate some of this line of thought into more ...
user avatar
0 votes
Accepted

There are infinitely many positive integers $a$ such that none of the integers $a, a+1,a+2$ are oddly powerful.

Apply CRT to the congruences: $$a\equiv 4 \pmod 8\quad \quad a+1\equiv 9\pmod {27}\quad \quad a+2\equiv 25\pmod {125}$$ For example. This yields $a\equiv 22148\pmod {(2\times 3\times 5)^3}$ Of course ...
user avatar
  • 62.8k
2 votes
Accepted

What is the sum of all $\alpha$ such that $5\mid(2^\alpha+\alpha)(3^\alpha+\alpha)$ and $\alpha$ is a positive whole number less than $120$?

Below we explain the key idea of the general method (stop at that paragraph for your hint). . Notice $\,\ 5\mid (2^n+n)(3^n+n)\iff 5\mid 2^n+n\,$ or $\,5\mid 3^n+n,\,$ by $5$ prime, hence we reduce ...
user avatar
1 vote

What is the sum of all $\alpha$ such that $5\mid(2^\alpha+\alpha)(3^\alpha+\alpha)$ and $\alpha$ is a positive whole number less than $120$?

EDIT: Well, I did make some errors which I have corrected below. Noodling. $2^4\equiv 3^4 \equiv 1 \pmod 5$. Case 1:So if $4\mid \alpha$ we have $2^\alpha \equiv 1\pmod 5$ and $3^\alpha \equiv 1\pmod ...
user avatar
  • 118k
1 vote

Number of solutions $x \in \{1,2,\ldots, 1000 \}$ of $ x^2(x+1)^2 \equiv 0 \pmod{1000}$

In order to determine the number of solutions, let's compute them for the prime powers that divide $1000$, namely $2^3$ and $5^3$. If $\#(f,n)$ denotes the number of solutions of $f(x)\equiv0$ modulo $...
user avatar
0 votes

Number of solutions $x \in \{1,2,\ldots, 1000 \}$ of $ x^2(x+1)^2 \equiv 0 \pmod{1000}$

Let $f(x)=x^2(x+1)^2$ $f(100+x)-f(x)\equiv 200x+600x^2+400x^3\equiv 200\,x\,(x+1)(2x+1)\pmod{1000}$ Yet we also have $f(x)\equiv 0\pmod 5\implies x\equiv 0\text{ or }4\pmod 5$ (by hand testing $0,1,2,...
user avatar
  • 24.7k
2 votes

Number of solutions $x \in \{1,2,\ldots, 1000 \}$ of $ x^2(x+1)^2 \equiv 0 \pmod{1000}$

Noting that $x$ and $x+1$ are relatively prime, one of $x^2$ and $(x+1)^2$ needs to be a multiple of $8$ and the other a multiple of $125$. This means that one of $x$ and $x+1$ must be a multiple of $...
user avatar
  • 37.4k
2 votes
Accepted

Proving representation of the same coset in $\mathbb{Z}[i]/(5)$ iff elements are congruent modulo $5$

I think your problem is simply a misapplication of the lemma you quote, the condition that $a+bi + (5) = a'+b'i + (5)$ is equivalent to the statement that $-(a+bi)+(a'+b'i) \in (5)$ (this lemma is ...
user avatar
  • 1,676
1 vote
Accepted

Inverse of 256 modulo 47 on $(a^{-1})^n \equiv (a^n)^{-1} \pmod p$

For a shortcut: $\,16 \cdot 3 = 48\,$, so $\,16^{-1} \equiv 3 \pmod{47}\,$, so $\,256^{-1}\equiv\dots\,$
user avatar
  • 70.2k
1 vote

Inverse of 256 modulo 47 on $(a^{-1})^n \equiv (a^n)^{-1} \pmod p$

A good thing about modulo is that you can keep subtracting 47 to get a smaller number. For example, $24^2=576\equiv 12 \pmod{47}$. Using this you can reduce $24^8$ mod 47.
user avatar
2 votes
Accepted

Surjectivity of the mod function

So $n$ is given, and we want to know whether for every $d\in\{0,1,...,n-1\}$ there is some prime $p$ such that $p\equiv d \bmod n$. Note that $p\equiv 0 \bmod n$ needs to have a solution too, and this ...
user avatar
1 vote

How to solve modular division when there is no inverse?

In general, $(a - b) \equiv mx\ mod\ n$ has $gcd(m,n)$ solutions ($mod\ n$) if $gcd(m,n)$ divides $(a - b)$ . The solutions are in arithmetic progression with difference between consecutive terms ...
user avatar
  • 11
0 votes

Taking modular square roots by CRT when modulus has many prime factors

I don't believe there is a method to easily derive all $16$ solutions from the $\,2\,$ you've found. However, we can generate them fairly quickly as follows. As explained here, applying CRT formula ...
user avatar
5 votes
Accepted

There exists a subsequence of every $n$ consecutive natural numbers whose sum is divisible by $n(n+1)/2$

Note: I'm assuming "subsequence" doesn't require contiguity, as otherwise the problem statement is false for $n=3$ and $(2,3,4)$. So, I'm interpreting "subsequence" to be ...
user avatar
2 votes
Accepted

What does "$A^b \bmod c$, where $A$ is a square matrix" mean? What is the modulus of a matrix?

It simply means to consider every element of $A^b$ in $\mathbb{Z}_c$, a.k.a. to take $\mod c$ over every term of the resulting $A^b$. This way, $A \in \mathbb{Z}^{n \times n}_c$, and $A^b \in \mathbb{...
user avatar
  • 2,236
2 votes

Egyptian unit decomposition + coverings of $\mathbb{Z}_P$ by arithmetic progressions

Let $d=gcd(a_1,..,a_n)$. Then, each residue class mod $d$ is covered by some subset. Let the subset $S_i\ (i=0,..,d-1)$ cover $P/d$ integers congruent to $i \pmod d$. Then, dividing all elements of $...
user avatar
  • 1,226
3 votes
Accepted

Can we generalize the quadratic formula to modular arithmetic?

You'll$\def\mod{\text{ mod }}$ get all solutions to $ax^2+bx+c = 0 \mod n$ by means of $x = \dfrac{-b +\sqrt{b^2-4ac}}{2a}, \tag 1$ provided that $\sqrt{r}$ is understood as the set of all solutions ...
user avatar
1 vote

can it be proven that $4^n \mod 15$ is equal to 1 for even n, 4 for odd n?

Generally, your procedure is right. But it is more precise to write as $$4^{2n} \equiv (16)^n \equiv 1^n \equiv 1 (\text{mod } 15).$$ Also, you can write $$4^{2n+1}\equiv(16)^n\cdot 4\equiv1^n\cdot 4\...
user avatar
  • 236
6 votes

Can we generalize the quadratic formula to modular arithmetic?

Yes, though it's not well-known (and despite incorrect claims to the contrary in other answers here) it is true that the quadratic formula (completing the square) can be used to solve modular ...
user avatar
2 votes

How to find $40! \mod 5^{10}$?

Because $5^9$ divides $40!$, we can use $ka \bmod kb =k(a \bmod b)\,$ [mod distributive law] to get $40! \bmod 5^{10} = 5^9\cdot(\frac{40!}{5^9} \bmod 5)$. Hence we really only need to find the ...
user avatar
5 votes

Can we generalize the quadratic formula to modular arithmetic?

Consider a concrete example: $x^2-5x+6=0\ (\operatorname{mod} 1000)$ A brute-force search gives the integer solution set $x \in \lbrace 2, 3, 378, 627 \rbrace\ (\operatorname{mod} 1000)$. The ...
user avatar
  • 8,553
0 votes

Missing a detail about Chinese Remainder Theorem and $Z$ Ring isomorphisms.

Firstly observe that the kernel of the map defined from $\mathbb{Z}$ is $m\mathbb{Z}\cap n\mathbb{Z}$ which is equal to $mn\mathbb{Z}$ only when $m,n$ are coprime.\ Secondly try to show that the map ...
user avatar
2 votes

How do you find out the number of solutions to $x^a \equiv b \pmod{n}$, $x^{12} \equiv 1 \pmod{27}$?

There is a general procedure to these type of problems. Observation. Suppose $(\mathbb{Z}/m\mathbb{Z})^\times=\langle g\rangle$ is cyclic and $\gcd(a,m)=1$. We want to find the solution to the ...
user avatar
0 votes

Remainder Dividing Repunits

First you find $\frac{1}{271} = .\overline{00369} = \frac{369}{99999} = \frac{41}{11111}$ The rest is "simple" arithmetic.
user avatar

Top 50 recent answers are included