New answers tagged modular-arithmetic
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 ...
- 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$$
- 3,787
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 ...
- 64.8k
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 ...
- 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) $
...................................
- 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, ...
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$, ...
- 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 ...
- 616
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 ...
- 616
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{...
- 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 ...
- 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]_{...
- 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 ...
- 6,435
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 ...
- 2,473
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 ...
- 97
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$.
- 31
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 \...
- 19
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.
- 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 $.
- 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 $...
- 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$.
- 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.
- 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.$ ...
- 2,473
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 ...
- 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 ...
- 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 ...
- 29.9k
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 ...
- 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 ...
- 258k
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 ...
- 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 $...
- 6,435
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,...
- 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 $...
- 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 ...
- 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\,$
- 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.
- 51
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 ...
- 11.4k
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 ...
- 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 ...
- 258k
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 ...
- 27.2k
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{...
- 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 $...
- 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 ...
- 6,435
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\...
- 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 ...
- 258k
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 ...
- 360
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 ...
- 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 ...
- 1,145
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 ...
- 51
0
votes
Remainder Dividing Repunits
First you find $\frac{1}{271} = .\overline{00369} = \frac{369}{99999}
= \frac{41}{11111}$
The rest is "simple" arithmetic.
- 25.8k
Top 50 recent answers are included