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$.
1,983
questions with no upvoted or accepted answers
110
votes
0
answers
4k
views
Finding primes so that $x^p+y^p=z^p$ is unsolvable in the $p$-adic units
On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem:
Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
- 3,465
36
votes
0
answers
738
views
Grasshopper jumping on circles
Can we characterize the grasshopper sequence?
Let $n\in\mathbb N$ be the number of stones $s\in\{0,1,2\dots,n-1\}=S$ on a circle that the grasshopper can jump on. Let $v(s)$ be the number of times ...
- 12.4k
27
votes
0
answers
913
views
Binomial coefficients modulo a prime
Consider an odd prime $p\equiv1 \pmod {16}$ and set $M=\frac{p-1}{2}$ for notational convenience. Then is there even a single prime $p$ of the above form for which the following congruence holds? $$\...
- 9,195
19
votes
0
answers
386
views
Conjecture: No positive integer can be written as $a^b+b^a$ in more than one way
Today, I came up with the following problem when trying to solve this.
Are there distinct integers $a,b,m,n>1$ such that the equation $$a^b+b^a=m^n+n^m$$ holds? That is, is there ever an integer ...
- 26.4k
14
votes
0
answers
310
views
Is $2p-2$ a period of $\{a_n\}$ modulo a prime $p$?
Let ${a_0}=1$, ${a_n}=\sum_{k=0}^{n-1} \binom{2n}{2k}a_ka_{n-k-1}$ for $n>0$. That is, ${a_n}=$ A002067(n) in OEIS.
Question: for any prime $p$, is $2p-2$ a period of $\{a_n\}$ modulo $p$?
And it ...
- 258
14
votes
0
answers
398
views
Properties of the remainders from division into primes
This is a question that has bothered me for almost 6 years now on and off, and I still don't really know enough to tackle it.
To phrase it somewhat formally:
Let $P$ be the series of prime numbers ...
- 51
14
votes
0
answers
277
views
All interval sequences mod integers
In music, an all-interval twelve-tone sequence is a sequence that contains a row of 12 distinct notes such that it contains one instance of each interval within the octave, 1 through 11. The more ...
- 2,733
11
votes
0
answers
209
views
Iterating $f(x) = P \bmod x$
Take a prime number $P \ge 3$ and some integer $x \in [1, P-1]$. Let's consider a sequence of values $x = x_0, x_1, \ldots, x_k = 1$, where $x_{n+1} = P \bmod x_n$ and the first occurence of $1$ ...
- 111
11
votes
0
answers
300
views
If $b$ is even and not a power of two, can $b^4+1$ be a weak pseudoprime?
The complete question is already in the title but we shall provide some motivation as well.
We study generalized Fermat numbers defined by:
$$\mathrm{GF}(n,b) = b^{2^n}+1$$
where $b$ and $n$ are ...
- 5,067
11
votes
0
answers
1k
views
Generalizing the Pell equation $x^2-61y^2 = 1$
In a table of fundamental solutions $f_1(x,y)$ to Pell equations,
$$x^2-dy^2=1\tag1$$
with $d<110$, two will stand out,
$$(U_{61})^6 = \big(\tfrac{39+5\sqrt{61}}{2}\big)^6 = x+y\sqrt{61} =...
- 52.3k
10
votes
0
answers
449
views
Prove $\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$ for $p$ being an odd prime
I need to prove the following:
$$\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$$
...with $p$ being an odd prime number. The statement is obviously true for$\pmod p$ because left-...
- 15.9k
10
votes
0
answers
454
views
Finite algebraic structures where all hyperoperations (addition, multiplication, exponentiation, tetration, etc.) are well-defined
Let $\langle R, +, \times, \uparrow, \uparrow\uparrow, \uparrow\uparrow\uparrow, \ldots; 0, 1\rangle$ be an algebraic structure with two constants $0, 1$ and where an infinite sequence of binary ...
- 5,631
10
votes
1
answer
576
views
Asymptotic Distribution of Prime Gaps in Residue Classes
Define $\pi_{n,a}(x)$ as the number of primes $p$ less than $x$ such that $p\equiv a\bmod n$ for coprime $n,a$. This function can be asymptotically approximated by $$\pi_{n,a}(x)=\frac{\operatorname{...
- 2,614
10
votes
1
answer
518
views
Reduction modulo p of a linear group over the rational numbers
A paper (http://arxiv.org/pdf/1407.3158v2.pdf) contains the following theorem:
Suppose $\mathbb{G}$ is a connected, simply connected, semisimple algebraic group defined over $\mathbb{Q}$, and let $\...
- 403
9
votes
0
answers
139
views
A mere coincidence? $\tan5^n<0$ for all $1\leq n \leq 23, n \neq 17$
I was playing around with $\tan e^n$ and realized that $\tan5^n$ has an interesting property:
$$
\begin{eqnarray}
\tan 5^{1}&=&-3.380515\ldots\\
\tan 5^{2}&=&-0.133526\ldots\\
\tan 5^{...
- 1,233
9
votes
0
answers
175
views
Polynomial detecting congruence conditions
It is well-known that a prime number $p$ is $\equiv 1 \pmod 4$ iff $p=x^2+y^2$ for some integers $x,y$ (except for $p=2$). My question is: is there an irreducible homogeneous polynomial $f \in \Bbb Z[...
- 6,100
8
votes
0
answers
164
views
Is there a simple formula for $\binom{2n}{n} \pmod{n^3}$?
Is there a simple formula for the following? $$f(n) = \binom{2n}{n} \pmod{n^3}$$
I know $f(n) = 2$ iff $n$ is prime and greater than $3$, but I don't know anything about composite numbers.
- 2,406
8
votes
0
answers
210
views
There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$.
I observed that if $n$ is a composite number of the form $6k + 1$ then there are at least three divisors of $n - 1$ which do not divide $\phi(n)$ (Euler's totient function). Is this true in general?
...
- 18.2k
7
votes
1
answer
177
views
I conjecture $3^{{2^n}}+1=2^1\prod_{k=1}^m p_k^1$ where $p_k$ are primes of the form $1+4k$, $k\in\mathbb{N}^*$
Let $T_n=3^{{2^n}}+1$, $n\geq 1$. I conjecture $$T_n=2^1\prod_{k=1}^m p_k^1$$ where $p_k$ are primes of the form $1+4k$, $k\in\mathbb{N}^*$. Note that the exponents on the $p_k$ are all $1$.
...
- 3,731
7
votes
0
answers
178
views
Could a nice principe, or at least a simpler alternative proof, be found regarding a lemma of Gauss
To prove the quadratic reciprocity law, Gauss needed the following lemma:
If $p$ is a prime number congruent to 1 modulo 8, then there exists a prime $q<p$ such that $p$ is a non residue modulo $q$...
- 1,764
7
votes
0
answers
229
views
Prime generating modular function
I found that
$(671n \mod 2454) + (304n \mod 32) + (4373n \mod 199)$
generates $38$ distinct primes for $n=1$ to $38$: $881, 1531, 2213, 409, 1091, 1741, 2423, 619, 1301, 1951, 179, 829, 1511, 2161, ...
- 1,965
7
votes
0
answers
255
views
Visualizing rational numbers as multiplication graphs
It's an interesting fact, that there's a straight forward way to visualize rational numbers. To each rational number – given as two integers $n<m$ – there corresponds a multiplication graph $n/m$ ...
- 17.9k
7
votes
0
answers
641
views
Period of Fibonacci sequence and Lucas number mod p
Let $p$ be an odd prime and $L_n$ be the $n$th Lucas number. Can anyone prove this?
$$\frac{L_1}{1}+\frac{L_3}{3}+\frac{L_5}{5}+\cdots+\frac{L_{p-2}}{p-2}\neq0\pmod{p}$$
Please help me!
I am ...
- 351
7
votes
0
answers
173
views
I found a way to calculate Quadratic min mod $N$, but why does it work?
I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:
$$a^2\equiv b(\mod{N})$$
If I am able to find $b$ that is a perfect square, I will be able to factor $N$...
- 1,440
7
votes
0
answers
164
views
Number Theory: $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$
I have this problem assigned for homework:
Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1<k<p-1$, then $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$.
I've come up with a proof ...
- 1,165
7
votes
0
answers
142
views
Statement about Woodall primes.
A Woodall number is an integer of the form $n 2^{n}-1$.
A Woodall prime is an integer that is both a prime and a Woodall number.
Let $p$ be a prime of the form 1 mod 4.
Then $p 2^{p} -1$ is never a ...
- 14.6k
6
votes
0
answers
117
views
Why do so many primes such that $2^q\equiv4\pmod{q+2}$ end in $7$?
Originally, I was investigating the divisibility of $p^q-q^p$ by $p+q$ for primes $p,q$, but I quickly discovered that even $p=2$ is not easy at all.
When $p=2$, we have $2^q-q^2\equiv0\pmod{q+2}\iff2^...
- 26.4k
6
votes
0
answers
93
views
Proof that $a^2+b^3+c^4=k$ modulo $m$ always has a solution
Question
Given integers $m\ge1$ and $0\le k<m$, I want to show that $a^2+b^3+c^4=k \pmod m$ always has a solution.
Attempt
It’s easy to show that it is enough to prove this when $m$ is a prime or a ...
- 9,176
6
votes
0
answers
293
views
Can long numbers be "3-palindromic"?
Question
Let $n$ be a number with $d\ge9$ digits when written in number base
$b\ge2$.
Can $n$ be $3$-palindromic? That is, does there exist $b$, such that
$n$ is simultaneously a ...
- 12.4k
6
votes
1
answer
128
views
Prove that there are at least $4(p-3)(p-1)^{p-4}$ functions $f:S\to S$ satisfying $\sum \limits_{x\in T} x^{f(x)}\equiv a \pmod p$
This question is the third round of Iranian exam questions, which has not been answered for several years now. I think there are many people here, which may be able to solve this problem.
From AOPS
...
- 92.6k
6
votes
0
answers
252
views
Modular geometry: The parabolas of quadratic residues modulo $p$
[For using the available space better, I rotated the function graphs by 90 degrees.]
For the quadratic function $f_1(x) = x^2$ (with $x \in \mathbb{R}$) there is only one parabola all integer points $...
- 17.9k
6
votes
0
answers
304
views
Question: How to find the smallest value $x$ satisfying the equation: $x^2 = a \pmod c$ (known is $a$ and $c$, $c$ is not the prime)?
Question: How to find the smallest value $x$ satisfying the equation: $x^2 = a \pmod c$ (known is $a$ and $c$, $c$ is not the prime)?
Using the Tonelli-Shanks algorithm and the Chinese remainder ...
- 469
6
votes
0
answers
114
views
Modular power tower mapping, is it injective?
Given an infinite sequence $a_1, a_2, \dots$ where all $a_i > 1$ we study $a_1^{\,a_2^{\,\cdots}} \bmod m$. While this is an infinite power tower that grows without bound, I argue that it can be ...
- 10.3k
6
votes
0
answers
535
views
Proof help: RSA Encryption
I am trying to fill in the middle of this proof:
$$ \begin{align}
m_1 ^e \mod N \cdot \left( m_2 ^e \mod N\right)^{-1}\mod N & = \\
& \quad \vdots \\
& = \left( \frac {m_1}{m_2}\right)^e\...
- 4,945
6
votes
0
answers
3k
views
How can I solve system of linear equations over finite fields in WolframAlpha?
Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that?
Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$.
If I want to solve this ...
- 52.6k
5
votes
0
answers
67
views
Sum of two squares mod p using primitive root
My question is as follows (Problem 5.2 in Aluffi, Algebra: Chapter 0):
Question. For any finite field $F := \mathbb{F}_{p^d}$, show that any element $k$ can be written as a sum of two squares, i.e. ...
- 388
5
votes
0
answers
329
views
Self-powers residues
Let $a$, $x$ and $n$ three positive integers such that $\gcd(a,n)=1$ and $x^x=a \mod n^n$.
Prove that we can find a positive integer $y$ such that $y^y=a\mod n^{n^n}$.
This is what I managed to prove ...
user14479
5
votes
0
answers
105
views
Proving that $\Sigma_{i=0}^{n-1} \alpha^i = 0$ for $k\mid n$ and $\alpha$ of order $k$
I've "found" the following theorem:
If $n$ is a composite number, $k$ is a divisor of $n$, and $\alpha$ an element of $(\mathbb Z/n)^\times$ of order $k$, then $$\sum_{i=0}^{n-1} \alpha^i = ...
- 1,764
5
votes
0
answers
69
views
For what $p$ is there a $d$ where $x^3+d$ is Hamiltonian in ${\mathbb Z}/p$?
Definitions
Let $p$ be a prime, and let $f:{\mathbb Z}/p\to{\mathbb Z}/p$ be a function. Then we say that $f$ is Hamiltonian in ${\mathbb Z}/p$ if the directed graph of $f$ is just one cycle --- a ...
- 2,817
5
votes
0
answers
161
views
Circles in $\mathrm{mod}\ 3$ "XOR-triangles"
This question is about a slight generalization of "XOR-triangles", which is the name the OEIS gives to the construction discussed in the MathOverflow question "Number triangle."
...
- 4,970
5
votes
0
answers
113
views
Why is it called the "congruence class", not "congruence set"?
Stupid question, why do we call it the congruence class, not congruence set?
Is there any scenario when the congruence class is not a set?
- 51
5
votes
0
answers
120
views
If $\forall n \in \mathbb{N}^*, \ a^n - 1 \mid b^n - 1$ therefore $\exists p \in \mathbb{N}^*,\ b=a^p$.
Let $a,b \in \mathbb{N}$ such that $2 \le a \le b$. Suppose $\forall n \in \mathbb{N}^*, \ a^n - 1 \mid b^n - 1$, show that $\exists p \in \mathbb{N}^*,\ b=a^p$.
I saw a solution using calculus (...
- 1,744
5
votes
0
answers
184
views
Polynomial zeros modulo a prime power
Let $p$ be a prime and $k,n$ integers $\geq 1$. Let $f(X)$ be a univariate degree $n$ polynomial in $(\mathbb{Z}/p^{kn}\mathbb{Z})[X]$ such that not all coefficients are divisible by $p$.
Is it ...
- 71
5
votes
0
answers
221
views
Complexity of repeatedly applying Euler's totient
When performing modular power towers e.g. $a_0^{a_1^{a_2^{.^{.^.}}}}\bmod n$, Euler's totient theorem and it's generalization reduces the problem to computing
$$n,\varphi(n),\varphi(\varphi(n)),\...
5
votes
0
answers
302
views
Defining the Equivalence of Categories
So, I'm trying to sort my head around this notion of equivalences of categories, and so I decided to construct a short and simple example for my own reference to kind of motivate why one would create ...
- 1,850
5
votes
0
answers
137
views
Sequence of positive integers $n$ such that $n^2+n+1$ divides $4^n+2^n+1$ and $n$ is not power two
If positive integer $n$ is not power two and $n^2+n+1 \mid 4^n+2^n+1$, then what sequence of $n$?
Source problem from Prove that there are infinitely many integers $n>0$ such that $n^2+n+1$ ...
- 1,636
5
votes
0
answers
168
views
A positive integer "modulo a sequence".
Motivation:
The (principal) value of
$$m\pmod{n}$$
for some positive integers $m> n$, might well be viewed as the value
$$m-\sum_{i=1}^{M_{m,n}}n,\tag{$\Sigma$}$$
for some $M_{m,n}\in \Bbb N$ ...
- 43k
5
votes
0
answers
154
views
About gaps between prime numbers
Consider some even integer number $n$.
Let: $$C = \{c_i|i - n \mod i\}_{i=2..n}$$
For example for $n = 50$:
$c_2 = 2 - 50 \mod 2 = 2$
$c_3 = 3 - 50 \mod 3 = 1$
$c_4 = 4 - 50 \mod 4 = 2$
$c_5 = 5 ...
- 265
5
votes
0
answers
78
views
In proving that $\sqrt{a}$ is always irrational, $\forall a\in\left\{\Bbb R^+ : 1< a\neq b^2\right\}$... a different way.
I was trying to prove the following statement: $$\sqrt{a}\text{ is always irrational, }\forall a\in\left\{\mathbb{R}^+ : 1<a\neq b^2\right\}.\tag{$b\in\mathbb{Z}$}$$ I know there is at least one ...
- 9,369
5
votes
0
answers
72
views
Finding an order-2 permutation that sorts colored balls
Suppose there are $M$ different colors of ball and you have $N$ of each kind. You arrange all of the balls in an arbitrary linear order. Is it always possible to find a permutation of order 2 such ...
- 17k