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$.
10,941
questions
0
votes
0
answers
45
views
Proof of the general case for Fermat's little theorem
I have proved Fermat's little theorem (F.L.T) that is "If $p$ be a prime, then $x^p=x\bmod p$ " by induction on x for $x \in \mathbb Z$ and $x \ge 0$. I want to prove the general case that ...
0
votes
0
answers
16
views
Find divisors using congruences
We have $n := 115921$ , $2^{\frac{n-1}{4}} \equiv 963 \pmod{n}$, and $2^{\frac{n-1}{2}} \equiv 1 \pmod{n}$. How would you calculate a divisor of $n$ and why will the method work correctly (...
1
vote
1
answer
60
views
Nonconstant polynomial $f(x) \in \mathbb{Z}[x]$ with $f(0)=1$, then there exists an $n \in \mathbb{N}$ such that $f(n)$ is divisible by 2021 primes.
I'm working on a problem which is stated as follows :
Let $f(x) \in \mathbb{Z}[x]$ be a nonconstant polynomial with $f(0)=1$. Then, there exists $n \in \mathbb{N}$ such that $f(n)$ is divisible by $...
- 35
4
votes
4
answers
360
views
find infinitely many (or all) positive integers n so that n and rev(n) are perfect squares
For a positive integer n, let rev(n) denote the integer obtained by reversing the digits of n. Find infinitely many (or all) positive integers n so that n and rev(n) are perfect squares.
The problem ...
- 95
0
votes
0
answers
19
views
Congruence properties
In congruence, we have this property:
(a ≡ b (mod m) and 0 ≤ b < m) ⇒ a = m . q + b
This says that for this
a ≡ b (mod m) and 0 ≤ b < m
We have that b is the remainder in the Euclidean division ...
- 11
-2
votes
0
answers
78
views
$37^{12} \bmod 23$ Mental Math Question
This question came from a mental math test, where you are not allowed to use a calculator or ANY scratch work.
$$37^{12} \bmod 23$$
Conventionally, when given a question like this, we can use ...
- 1
3
votes
1
answer
70
views
Modular equations and Euler's theorem
Looking at group $U{81}$ find $0<x<81$ such that:
$$x^{19}=8 \:(mod\:81)$$
I know that $o(8)=18$, is it true to say:
$$(x^{19})^{18}=1 \:(mod\:81)$$
and from here to use Euler's theorem which ...
- 99
0
votes
0
answers
24
views
How to determine if a number is a multiple of 19 [duplicate]
How to determine if a number is a multiple of 19.
Could you use some method from divisibility or other method in number theory to find a formula or a procedure to determine if the number is a multiple ...
1
vote
0
answers
44
views
Showing that $1+a+a^2+\cdots+a^{\phi(m)-1}\equiv0\bmod{m}$ if $\gcd(a,m)=\gcd(a-1,m)=1$ [duplicate]
Show that for $a \in \mathbb{Z}, m\in \mathbb{N}$:
$$1+a+a^2+...+a^{\phi(m)-1} \equiv 0 \mod{m}$$ if
$\gcd(a,m)=\gcd(a-1,m)=1$.
The relation is trivially true for $m=1$. For $m \geq 2$ we know from ...
- 19
0
votes
2
answers
143
views
Are there infinitely many $c$-th perfect powers having a constant congruence speed of $c$?
Let $a$ be a positive integer of the form $20 \cdot n + 5$ (i.e., $a : a \equiv 5 \pmod {20}$, $n \in \mathbb{N}_0$). I wish to prove (or disporove) the following statement.
Let $c \in \mathbb{Z}^+$ ...
- 563
1
vote
0
answers
18
views
Modular exponentiation to shuffle list
Can modular exponentiation be used to shuffle a list? I have noticed that modular exponentiation sometimes repeats every number only once, and therefore works like a shuffle mechanism for a list. I do ...
- 121
0
votes
0
answers
6
views
Finding smaller pseudofactors modulo N
In the paper "Shor's algorithm with fewer (pure) qubits", Zalka points out that a multiplication by an arbitrary constant $C$ modulo $N$ can be reduced in cost by finding smaller values $c_1$...
- 2,104
1
vote
0
answers
46
views
Find which number is greater over modulus
Let's say I have two numbers a(=2) and b(=9) (b > a).
Mod calculations are being done with k=11. Also, ...
- 11
1
vote
1
answer
67
views
Solving the congruence $3x \equiv 17 \pmod{29}$ [duplicate]
The given linear congruence is to be solved:
$$\gcd:(3;29)=1 |17$$
$$3x+29y=1 \iff 3x \equiv 1 \pmod{29} \iff y \equiv 3^{-1} \pmod{29}$$
With the extended Euclidean algorithm one obtains:
\begin{...
- 25
3
votes
4
answers
193
views
Generating residues with $ a^n + b^n \mod p $
Say there exist some non-zero distinct residues $a,b$ such that
$$ a^n + b^n \mod p $$
generates all nonzero residues for some $n$.
Does such a pair $a,b$ exist for every odd prime $p > 13$ ? Or ...
- 14.2k
-1
votes
0
answers
28
views
Why there exists a nonempty subset divisible by $m$ when the length of list of positive integer is at least $m$? [duplicate]
I have a list of positive integers where $n$ is the length of the list. I have to take a nonempty subset such that its sum is divisible by $m$. I noticed that if $n \geq m$, the claim holds. But I don'...
- 651
2
votes
0
answers
32
views
The first Galois cohomology commutes with projective limits
I am reading Serre's paper "Sur les groupes de congruence des variétés abéliennes" (here is the link to this paper: https://www.mathnet.ru/links/016949238724700ec2209f00e507a40f/im3061.pdf). ...
- 324
0
votes
0
answers
94
views
solutions to $x = \sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$
Fix an integer $0<a<p-1$, and an odd prime $p$.
Define
$$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$
to be the set of all integers $x\in\{0,...,p-1\}$ such that, for some ...
- 14.2k
2
votes
1
answer
64
views
How to represent and compare 'subsets of a group with modulo'?
For a group $G$ with operation $+$, I'm interested in the set $\mathscr H$ of its subsets that can be constructed using only the following two rules:
$\{g\}$ (so a singleton set) is in $\mathscr H$ ...
4
votes
2
answers
113
views
Show that there are no two positive integers $x$ and $y$ such that $x^3=2^y+15$.
Show that there are no two positive integers $x$ and $y$ such that $x^3=2^y+15$.
Attempt
For the sake of contradiction, suppose that there are two positive integers $x$ and $y$ satisfying $x^3 = 2^y + ...
- 289
1
vote
0
answers
49
views
What is the minimum modulus where the first $n$ values of Fibonacci sequence are still unique?
Using the sequence $F_1 = 1, F_2 = 2, F_n = F_{n-1} + F_{n-2}$
$$
1, 2, 3, 5, 8, 13, \ldots
$$
What is the smallest modulus $M$ for each $n$ such that this sequence $S_n = F_n \mod M$ has no ...
- 1,263
0
votes
1
answer
49
views
Diagonalizing matrices over $\mathbb{Z}/ p^k$
Let $p$ be an odd prime and $A$ a symmetric matrix in $M_{n\times n}(\mathbb{Z}/ p^k)$. How does one prove there exists a matrix $M \in GL_n(\mathbb{Z}/ p^k)$ such that $M^tAM$ is diagonal?
I do not ...
2
votes
0
answers
56
views
Finding prime numbers with mod function with respect to given odd number $'a'$ between $2^n$ and $2^{n+1}$
Here are few steps which made sense when analysing the prime numbers
Step 1: For any odd number "$a \in Z^+ $" e.g. 17
Step 2 : $a$ is $2^{n} < a < 2^{n+1}$
Step 3: now get the list ...
0
votes
1
answer
54
views
Number of cycles of doubling map mod n
Playing with some rhythm ideas, I stumbled on the sequence A000374. It claims that the number of cycles of $f(x) = 2x \bmod n$ is the same as the number of distinct irreducible factors of $x^n - 1 \...
- 681
0
votes
1
answer
85
views
Why in cryptography we use modular arithmetic for encryption? What's the intuition behind it?
I was studying various cryptographic encryption schemes and why modular arithmetic is being used so much while encrypting messages. Why don't we use simple multiplication with a large known prime with ...
-3
votes
1
answer
58
views
Why only numbers coprime with n in A mod n have modular inverse? [duplicate]
Why do only the numbers coprime to n (numbers that share no prime factors with n) have a modular inverse (mod n)? Can anyone intuitively explain it?
1
vote
1
answer
93
views
$a_k = 8^{3k} + 8^{3k-1}+8^{3k-2} $ [duplicate]
Let $a_k = 8^{3k} + 8^{3k-1}+8^{3k-2} $, with $k$ being a natural number greater than $0$.
Determine all $k$ such that $6 \ | \ a_k-2$.
My attempt is to reduce $8$ as
$8\equiv 2 \bmod 6$.
Then we can ...
- 153
1
vote
1
answer
64
views
Closed-form expression for sum of Modulo Arithmetic Progression
Is there any closed-form expression or atleast an efficient way to calculate this sum?
$$ \sum_{i=1}^{N} (a \cdot i) \bmod{M} $$
we can assume $N$, $a$, and $M$ are large enough such that simple ...
- 15
-1
votes
1
answer
92
views
$a$ mod $b^{n}$ - $a$ mod $b^{n-1}=0$ [closed]
The problem is stated in the title and another thing to consider is that $n$ (as well as $a$) might be too large. Computing $b^{n}$ would therefore be infeasible.
Is there any trick or observation one ...
-1
votes
0
answers
23
views
High power modulo [duplicate]
I know euler and fermat theorems about this subject but it doesn't help me, how you calculate:
$7^{565} mod (380)$
I did reduction with euler function and got to $7^{143} = (7^{11})^{13}
mod(380)$ ...
- 99
-3
votes
1
answer
47
views
What is a solution of $7X\equiv 34 \mod{45}?$ [duplicate]
I just need a solution but it seems like I cannot get. I tried Euclid algorithm and Euler's theorem but no progress.
- 1
-2
votes
0
answers
117
views
What are the last three digits of $13^{251}$? [duplicate]
I need some help with this. I used Euler's theorem and managed to get $13^{400} \equiv 1 \mod{1000}$ and reduce it to $13^{51}$ but after that I have no idea how to solve it.
- 1
0
votes
0
answers
35
views
Modular Arithmetic Simplify [duplicate]
Congruence is an equivalence relation so transitive, so $\,x^2\equiv 79,\ 79\equiv 2\Rightarrow x^2\equiv 2,\,$ see the linked dupe.
I was wondering how in number theory we are able to determine how ...
1
vote
0
answers
30
views
$X^d\equiv T\pmod P \Longleftrightarrow P(0)$ is a $d$-th power [closed]
Suppose $d$ is a positive integer and that $q\equiv 1\pmod {4d}$. Let P be a monic irreducible polynomial in $\mathbf{F}_q[T]$. Is the following statement correct?
$X^d\equiv T\pmod P$ is solvable $\...
- 11
3
votes
1
answer
173
views
When $4^x+9^y$ is a multiple of $37$?
How to find all $(x,y) \in \mathbb Q^{\geq 0} \times \mathbb Q^{\geq 0}$ such that $4^x+9^y$ is a multiple of $37$ ?
Let $u=2x,~v=2y$, then the problem reduces to $$2^u+3^v \equiv 0~(\text{mod}~37)~--...
- 353
-1
votes
1
answer
36
views
Proving modular arithmetic property over large sums [duplicate]
How can I prove that:
$$ ((a + b)\bmod{2} \; + \;c)\bmod{2} = (a+b+c)\bmod{2} $$
I am unsure of the name of this property, but I realized I know this by intuition. The reason for this is that I want ...
- 304
-1
votes
1
answer
25
views
First collision of modular sequences [duplicate]
Suppose I have a binary $s$ sequence described by $P$ and $o$: $s_n = 1 \iff n \equiv o \pmod P$.
Given two such sequences $s^1$ and $s^2$ described by $P_1, o_1$ and $P_2, o_2$ respectively, I want ...
0
votes
1
answer
57
views
How can I prove this regarding Cyclotomic Cosets?
For a positive integer $n$, let $[n]$ denotes the set $[n]:=\{1,2,3,...,n\}$.
Let $m$ be a positive integer, then define a set $A$ as
$$A:= [2^m - 2]\big\backslash [2^{m-1}-2]$$.
Now, define the ...
- 379
0
votes
0
answers
57
views
All values of $x$ [duplicate]
So I just learned about modular arithmetic today and I was solving a system of congruences probably that you saw before.
the statement was
$n ≡ 3\pmod5$
$n ≡ 1\pmod 7$
$n ≡ 6\pmod8$
writing this again ...
- 23
1
vote
1
answer
32
views
Randomness of rightmost bits from LCGs
Task: Show that the sequence of integers made up of the $k$ rightmost bits generated by an LCG with $m = 2^n$ has a period of at most $2^k$.
I actually get a hint to define the output as the following:...
- 857
1
vote
0
answers
30
views
Elliptic Curves - can point addition never hit the third point?
Can it so happen that "adding" two points of Elliptic Curve (over finite field) never "hits" any third point of that curve? For example ...
-1
votes
4
answers
110
views
The number of positive integers n less than or equal to $22$ such that $7$ divides $n^5 +4n^4 +3n^3 +2022$
I tried using the fact that if $f(n)$ is divisible by $7$ then so will $f(n+7)$. So 1, 8, 15, 22 can all come out to be solutions once we see that $1$ is a solution. Continuing this $2$ also satisfies ...
- 157
0
votes
0
answers
41
views
What are all solutions of $3^n \equiv -1$ (mod $10$)? [duplicate]
Consider the congruence equation $$ 3^x \equiv -1~(\text{mod}~10).$$
What are the solutions ?
We can see $x=2$ is a solution and thus by cyclic property $2+10k,~k \in \mathbb Z$ should be a solution....
- 353
-1
votes
0
answers
19
views
reductions modulo p involving fractions [duplicate]
Given a prime number p > 3 and primitive root of p, r, I know (from some previous argument) that
$$\frac{1-r^{p+1}}{1-r^2}$$
is a whole number. For context, I know this by the geometric series ...
- 105
-1
votes
2
answers
29
views
Polynomial Congruence Equation
Struggling with this question: $15x^3 -6x^2 + 2x +26 \cong 0 \mod343$.
Here is what I have so far:
By Hensel's Lemma if we have a solution to $f(x) \cong 0\mod p$ we can find solution to $f(x) \cong 0\...
- 9
1
vote
2
answers
62
views
When is $\{x^2+y^k \mod n: x,y \in \mathbb{Z}/n\mathbb{Z}\} \neq \mathbb{Z}/n\mathbb{Z}$?
This question came about when I played around with the classic statement
$$\exists x,y \in \mathbb{Z}: x^2+y^2 = n \implies n \not\equiv 3 \mod 4$$
which is straightforwardly shown to be true by ...
- 775
0
votes
0
answers
25
views
Novice question regarding Rivest Shamir Wagner Time Lock Puzzles of the form $x^{2^t} \bmod N $ with $ N=p.q $ primes.
I'm using the Rivest Shamir Wagner Time Lock Puzzle setup in an application. The puzzles are of the form: $x^{2^t} \bmod N $ with $ N=p.q $ and p and q are primes.
My question is this: assuming I ...
- 101
0
votes
0
answers
14
views
Is there an efficient way to find x given mod(ax;b)=c? [duplicate]
It'll be the same thing as solving ax+by=c.
There's an algorithm to find gcd(x;y) with it you can solve that equation but it is very long for some pairs of numbers.
Of course a,b,c,x,y are all ...
1
vote
0
answers
60
views
For any integers $x$, $n$ greater than 1, there exists a positive integer $y$ such that $x + y \equiv 0 \pmod{n}$
Question: Prove or disprove the statement: "For any integers $x$, $n$ greater than 1, there exists a positive integer $y$ such that $x + y \equiv 0 \pmod{n}$."
Proof: Let $y \equiv -x \pmod{...
- 51
2
votes
2
answers
56
views
Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$.
Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$.
Here $\left(\frac{z}{q}\right)$ is the Legendre symbol whose value of 1 ...
- 339