Questions tagged [modular-arithmetic]
Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $a-b$.
13,386 questions
5
votes
5
answers
361
views
$2^n+1=3m^3$ has only one solution $(n,m)=(1,1)$
See that $(n, m) = (1, 1)$ is a valid positive integer solution to the Diophantine equation:
$$2^n + 1 = 3m^3$$
I am interested in proving that this is the only solution for $n, m \in \mathbb{Z}^+$. ...
- 1,724
0
votes
1
answer
52
views
What are the possible structures of covering systems of $\mathbb{Z}$ with $k$ residue classes?
A covering system of ℤ is a finite collection of residue classes
$a_1\mod{n_1},a_2\mod{n_2},\ldots,a_m\mod{n_m}$
whose union is $\mathbb{Z}$.
I am trying to understand how the structure of such ...
- 33
3
votes
1
answer
110
views
$\gcd$ is (almost) continuous in Furstenberg's topology in one argument (simple proof inside), but is it continuous in two variables simultaneously?
Extend $\gcd$ to all of $\Bbb{Z}^2 \to \Bbb{Z}$ in the standard way, or whatever way makes this work out.
Now we know that the topology $\phi$ on $\Bbb{Z}$ generated by open balls of the form $a +b\...
1
vote
1
answer
122
views
How can we find rational (or integer) parametrization using only "pen and paper"-based calculation for an elliptic curve $Y^2=X^3-3c^4X-(c^{10}+c^2)$?
This type of elliptic curve arises from Euler's 4th power taxicab number solution. I will suggest an attempt at a solution $$P^4+Q^4=R^4+S^4$$ $$\begin{cases} P=(a+b) \\ Q=(c-d) \\ R=(a-b) \\ S=(c+d) ...
0
votes
0
answers
51
views
Prove the invariance of arbitrary polynomial and nested digit-sum compositions under the projection $\pi:\mathbb{Z} \to \mathbb{Z}/(b-1)\mathbb{Z}$
Let $b > 1$ be an integer, and let $s_b(n)$ denote the sum-of-digits function base $b$.
Let $s_b^{\circ k}$ denote the $k$-th iterated $s_b$: $s_b\circ s_b \circ \dots \circ s_b (n)$, for any ...
- 1,724
1
vote
3
answers
181
views
How can one find numbers that multiply to a string of $1$, like $271 \times 41=11111$? [closed]
I recently had a question in my test, which was:
Find the remainder when the number $\underbrace{11111 \cdots 11111}_{n\text{ digits}}$ is divided by $271$.
Seeing this question, I completely ...
- 338
0
votes
0
answers
38
views
Does this finite quotient determine the next transition in an affine residue system?
Let
D = 3^17
and consider quotient representatives
0 <= C < D.
For each C, define <...
- 1
2
votes
2
answers
175
views
Near-cyclic numbers under multiplication by $2$ and digit rotation
The cyclic number
$$
142857 \cdot 2 = 285714
$$
can be interpreted as a perfect digit rotation:
$$
2n = R_2(n),
$$
where $R_q(n)$ denotes the left cyclic rotation of the decimal digits of $n$ by $q$ ...
- 29
7
votes
4
answers
442
views
No solutions of $(n^2+1) \mid (2^n+n)$ when $n>0$ (A solution was found)
I am interested in the divisibility problem $(n^2+1)\mid(2^n+n)$ for $n>0$.
Some immediate conditions: If $n$ is odd, then $n^2+1$ is even but $2^n+n$ is odd, so $n$ must be even. Moreover, if $p\...
- 1,724
0
votes
0
answers
41
views
Structure of base-$B$ representations modulo $B^2 - 1$ and a digit-folding congruence
I came across the following identity while studying arithmetic reductions in positional numeral systems.
Let $B \geq 2$, and consider an integer written in base $B$:
$$x = aB^2 + bB + c$$
with $0 \le ...
0
votes
0
answers
25
views
Closed form for a Beatty sum and for the rank in Fibonacci modular permutations
Setup: Let $M = F_{2r+1}$, $a = F_{2r}$. Define $R_b \equiv ab \pmod M$ for $0 < R_b < M$. The partial rank is given by $\rho_b = 1 + \#\{k < b : R_k < R_b\}$.
Main Result:
Let $\varphi = \...
0
votes
1
answer
162
views
Factoring method with triangular numbers & the complexity of finding a triple of triangular numbers to factorize an integer
I have been experimenting with a factorization approach based on the triangular number theorem (the "Eureka" theorem), which states:
Every positive integer can be represented as the sum of ...
0
votes
1
answer
67
views
Primes in limited modular residue classes
Task
Find a natural number $n>25$ with the property that we can select to each odd prime $q_1=3,q_2=5,\ldots,q_k$ less than $\sqrt{2n}$ a single remainder $a_1,a_2,\ldots,a_k$, $0<a_j<q_j$, ...
- 183
-3
votes
1
answer
106
views
Does equality of determinants of matrix powers modulo $n$ imply equality of the matrices modulo $n$? [closed]
Let $A \in M_p(\mathbb{Z}/n\mathbb{Z})$.
Is it true that
$$\det(A^k)=\det(A^j)\implies A^k=A^j?$$
In other words, does equality of determinants of matrix powers imply equality of the matrices ...
- 154
4
votes
1
answer
215
views
When is $a^b\equiv a^{(b\bmod n)}\mod n$?
Had a student tell me that the last digit of $9^{52}$ is $1$ (which it indeed is) since the last digit of $52$ is $2$ and the last digit of $9^2$ is $1$. Which raised the general question: when is $a^...
- 163