Skip to main content

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$.

Filter by
Sorted by
Tagged with
1 vote
1 answer
46 views

If a = b mod s and a = b mod t, why must s and t be relatively prime for a = b mod st?

In the problem (below) we are asked to show: if $a \pmod {st} = b \pmod {st}$, then $a \pmod s = b \pmod s$ and $a \pmod t = b \pmod t$. I did this part of the question. Then we are asked, what makes ...
Snoop's user avatar
  • 135
0 votes
1 answer
9 views

How big can the girth be on this graph class?

Let $G$ be a simple graph with vertex set $\{u_1, \dots, u_n\} \cup \{v_1, \dots v_n\}$, with $G_{\uparrow U}$ (subgraph induced by $U$) and $G_{\uparrow V}$ being cycles of size $n$. Now we want to ...
Qise's user avatar
  • 498
-1 votes
1 answer
65 views

Sum of modular multiplicative units [closed]

Given the sum $$g(n)=\sum_{a \in \mathbb{Z}^{*}_n}a$$ where $\mathbb{Z}^{*}_n$ is the multiplicative modular unit group. I want to know: is there some standard function or symbol representing it? any ...
David Lemon's user avatar
0 votes
0 answers
24 views

Does multiplying by n in a mod(n) equation the same as multiplying by 0? [duplicate]

The book is now explaining the multiplicative inverses in modular arithmetic, how if a number s has an inverse,t,modulo n, then it follows that $s*t≡ 1$mod(n). From that definition the book shows that ...
Jery Lazman's user avatar
0 votes
0 answers
12 views

Question on maths behind Floyd Cycle Finding Algorithm [duplicate]

So in our class our professor asked us a quesiton on the logic behind Floyd's Cycle Algorithm. FCA is based upon two pointers, one slow and one fast pointer, both of these pointers traverse the linked ...
Aadil's user avatar
  • 1
1 vote
1 answer
62 views

Show $x^p-x$ is not in $\ker\Psi_p$

Let $p\in\mathbb{P}$ be a prime integer. Let $\Psi_p:\mathbb{Z}[x]\to\mathbb{F}_p[x]$ be the homomorphism of reduction mod $p$. Show that the polynomial $x^p-x\in\mathbb{Z}[x]$ is not in $\ker\Psi_p$ ...
user926356's user avatar
  • 1,494
2 votes
2 answers
98 views

Last two digits of a sequence [closed]

Consider the sequence $$ a_{1} = 1,\,\ a_{n+1} = n^{\large a_n},\,\ \ {\rm so}\,\ \ a_{2} = 2^{1},\,\ a_{3} = 3^{2^{\large 1}},\,\ a_{4} = 4^{\large 3^{2^{1}}} \qquad$$ How can we find the last two ...
AgnostMystic's user avatar
  • 1,736
1 vote
0 answers
55 views

Confusion for algorithm for finding (a div d) and (a mod d), where a is an integer and d positive integer.

From Rosen's discrete Math textbook. I'm confused on 3 things regarding this algorithm (as can be seen via the screenshots) Why do we need an algorithm for finding $a$ div $d$ and $a$ mod $d$ when we ...
Bob Marley's user avatar
-1 votes
0 answers
39 views

Fermat's little theorem and Chinese Remainder Theorem [duplicate]

Find an integer $d$ such that $(M^{11})^d \equiv M$ (mod $55$) for all $M$ prime to $55$. I've gotten to this where $(M^{11})^d \equiv M$ (mod $5$) and $(M^{11})^d\equiv M$ (mod $11$) where this ...
Nethanel 's user avatar
1 vote
1 answer
57 views

How to check for solutions of non-linear systems over the integers modulo m?

We have the following system of 3 equations and 5 unknowns: $\left\{\begin{array}{lcl} u^2 + w^2 + x^2 + y^2 & = & 0\\ w^2 + x^2 + y^2 + z^2 & = & 1 \\ u^2 + x^2 + y^2 + z^2 & = &...
ERMTMG's user avatar
  • 11
0 votes
1 answer
61 views

Simplifying a reciprocal of a product of two quadratics using modular arithmetic

This is the fraction I'm trying to simplify mod q: $\frac{1}{(k^{2a} + k^a + 1)(k^{2b} + k^b +1)}$ and we have that $k^5 = 1 \bmod q$, $k ≠ 1 \bmod q$, and that $a$ and $b$ are integers where $a ≠ b$ ...
Polom Mata's user avatar
1 vote
1 answer
50 views

Natural way to extend the ring $\mathbb{Z} / p^k \mathbb{Z}$ so that the equation $x^2 + 1 \equiv 0 (\text{mod }p^k)$ has a solution

We know that for $p \equiv 3 (\text{mod }4)$, there is no solution to $x^2 + 1 \equiv 0 (\text{mod }p^k)$ for $k = 1, 2, \ldots$, by quadratic reciprocity. But can I embed the ring $\mathbb{Z} / p^k \...
John Jiang's user avatar
0 votes
1 answer
67 views

Finding BCH code syndromes

I' m not getting how syndromes are calculated for bch codes so I tried finding examples but still I don't seem to have it To calculate the first syndrome for the received message polynomial $R(x)=1+...
user159729's user avatar
-1 votes
0 answers
39 views

Do you need to add or multiply for the congruence to hold? [duplicate]

I was studying the basics of number theory from a book and it showd a Lemma that says the following: Given $a \equiv b\mod (n)$ and $c \equiv d \mod (n)$.Then: $$a+c \equiv b+d \mod(n)$$ $$ac \equiv ...
Jery Lazman's user avatar
0 votes
0 answers
31 views

Solve system of linear equations modulo n

Suppose I have a positive integer $n$ and a system of linear equations over $n$, i.e., $Mx \equiv c \pmod n$ where $M$ is a matrix and $c$ is a vector. Given $M,c,n$, is it possible to solve this ...
D.W.'s user avatar
  • 5,277
1 vote
0 answers
42 views

Solving $x^a\equiv b \pmod {p^m}$ [duplicate]

I am studying number theory by my own (I'm not a math major but I'm very interested in this, so I'm sorry I don't know much) and I was wondering if there is a result that says if this next equation ...
user286046's user avatar
-2 votes
1 answer
61 views

Show that $11^{n+2}+12^{2n+1}$ is divisible by 133 for any natural 'n'. [duplicate]

I found this practise problem on the internet and was not sure about the way to solve it, it was given under the topic of congruences but I was thinking of using induction. I have been trying this for ...
Sevensiren's user avatar
-4 votes
1 answer
85 views

How to prove that all elements inside a cycle of a cyclic group are different from each other [closed]

Let $G$ be a finite cyclic group $(G, \circ)$ and $a \in G$: $$ \langle a \rangle = \{a^z : z \in \mathbb{Z}\}, $$ and $\operatorname{ord}(a) = \min\{a^n : n \in \mathbb{N}_+\}$, i.e., the smallest ...
student129's user avatar
0 votes
1 answer
57 views

Why is the order of an element equal to the order of the group it generates? [duplicate]

I've found this post Prove the order of an element is the order of the group but this does not help me. Let G be a finite group (G,$\circ$) and a $\in$ G. $ \langle a \rangle $ = {$a^z$ : z $\in \...
student129's user avatar
0 votes
2 answers
72 views

Question involving Fermat's Little Theorem [duplicate]

Q: Show that if $p$ is an odd prime, then $2p$ divides $(2^{2p-1}-2)$. Here is how I approached the problem. Let $m=2p$. Then, $$2^{m-1}-2\pmod m$$ By Fermat's Little Theorem, $$2^{m-1}-2\equiv 1-2\...
k endres's user avatar
5 votes
4 answers
208 views

Factors of a quadratic in modulo $9$

Prove: If $a$ is any integer and the polynomial $f(x) = x^2 + ax + 1$ factors mod $9$, then there are three distinct non-negative integers $y$ less than $9$ such that $f(y) \equiv 0 \pmod 9$. I'm ...
Piratelubber's user avatar
1 vote
2 answers
52 views

If $d\mid10a-1$ then $d\mid10q+r\iff d\mid q+ar$ [duplicate]

$d\mid10a-1$. Proof that then $d\mid10q+r$ if and only if $d\mid q+ar$ My attempt was to go once in this direction: $$d\mid10a-1 \wedge d\mid10q+r\implies d\mid q+ar$$ and then with this: $$d\mid10a-...
Piotr Wasilewicz's user avatar
1 vote
0 answers
121 views

An interesting bijective function on $\Bbb Z_{26}$

In order to get the last letter of any italian tax code it is used the following bijective function on $\Bbb Z_{26}$. $f:\Bbb Z_{26}\to\Bbb Z_{26}$ defined as follows : $f(0)\!=\!1,\,f(1)\!=\!0,\,f(2)\...
Angelo's user avatar
  • 12.5k
3 votes
1 answer
91 views

Is $\sqrt{2}$ an element of the set $\{k \bmod 2\pi \mid k \in \mathbb{N}\}$? [closed]

I'm exploring the properties of the set formed by taking the modulo $\pi$ of natural numbers, specifically $\{k \bmod 2\pi \mid k \in \mathbb{N}\}$. This set includes all values $k - 2n\pi$ where $0 \...
hans's user avatar
  • 213
1 vote
0 answers
31 views

Solutions of the multivariable congruence equation

Given a prime $p$ and integers $p>a_1, \ldots, a_n, a_{n+1}>0$, I have to compute and store all the solutions in $\mathbb{Z}/p\mathbb{Z}$ of the following equation: $$ a_1x_1 + \dots + a_nx_n = ...
Cofinite's user avatar
2 votes
1 answer
115 views

How can I convert Interval Difference to Circle of Fifths segments and position

How to convert Interval Difference to Circle of Fifths segments and position Hi, Im designing a numeric decimal notation code model for exploring math relations between notes on chromatic scales and ...
AstroD's user avatar
  • 31
1 vote
3 answers
86 views

Calculate the last 2 digits of the following expression [duplicate]

Find last 2 digits of the following expression with modular arithmetic. $$\LARGE 7^{7^{7^{7}}} - 7^{7^{7}} - 7^7 - 7$$ I have tried taking remainders of all terms $\mod 100$ then subtracting , ...
Aryan Malik's user avatar
0 votes
2 answers
72 views

What is the order of $p_{1}^{x} \bmod{n}$ where $p_1$ is a prime factor of $n$ [closed]

I am looking for a formula, algorithm, or even literature on the topic. Take $21$ for example $21 = 7 \cdot 3$ What is the order of $3^{x} \bmod 21$? $3^0 = 1$ $3^1 = 3$ $3^2 = 9$ $3^3 = 6$ $3^4 = 18$...
zakrea2070's user avatar
0 votes
0 answers
39 views

How to determine if a solution exists for a system of two modular linear diophantine equations

The problem is to solve for $x$ and $y$: $x+2y\equiv 3 \pmod {10}$ and $3x+y\equiv 2 \pmod {10}$. I solved for the same equations modulus 9, using a matrix and row operations. But modulus 10, I don't ...
k endres's user avatar
0 votes
1 answer
46 views

Solving $a = x \mod b$ without congruences [duplicate]

I have never dealt with congruences, and I want to stay as pragmatic as possible here. Using a similar approach to trigonometric equations, where the solution is rather a set of answers that fulfil ...
Michel H's user avatar
  • 342
0 votes
1 answer
68 views

Examining whether the relation "$aRb$ iff $a + 2b \equiv 0 \pmod 3$" is reflexive, symmetric, antisymmetric, or transitive [duplicate]

Have I shown correctly which properties the relation fulfills? $$aRb \text{ iff } a + 2b \equiv 0 \pmod 3$$ $(1)$ Reflexivity Set $b=a$ $a + 2a = 3a \equiv 0 \pmod 3$ Hence, the relation is reflexive....
einzigartigerhummer's user avatar
1 vote
0 answers
58 views

Finding $\displaystyle\sum_{k=1}^{5}k^{99}\pmod{5}$ [duplicate]

This problem is from a great book: $$\color{rgb(128,128,255)}{\text{Discovering Higher Mathematics}}\\\color{rgb(255,128,128)}{\text{Four habits of Highly Effective Mathematicians}}\\\text{By }\color{...
Hussain-Alqatari's user avatar
0 votes
3 answers
103 views

Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p? [closed]

Given an odd prime $p$, a positive integer $1 \lt n$, and an integer $x \in \mathbb{Z}/p^n\mathbb{Z}$, does there exist an an integer-coefficient polynomial that extracts the highest digit of $x$? The ...
fofo's user avatar
  • 9
2 votes
1 answer
32 views

Help with understanding the solution set of a lemma [duplicate]

I am reading Linear Congruences in Dudley's Elementary Number Theory. I am having trouble following a part of the proof. There is another theorem referenced in the proof I will call Theorem 4.5: If $...
k endres's user avatar
1 vote
0 answers
63 views

About the equation $2^{n+1} = 3^p(2k+1)-1$

Let $k\in \mathbb{N}$. Can we always find $(n,p) \in \mathbb{N}^2$ such that : $$2^{n+1} = 3^p(2k+1)-1$$ For $k=0$ the couple $(0,1)$ works. For $k=1$ the couple $(0,0)$ works. For $k=2$ the couple $...
LexLarn's user avatar
  • 825
0 votes
2 answers
83 views

$ a^2 + p b^2 = c \mod p^2 $ is always solvable?

Let $p$ be an odd prime number. Let $c$ be a given integer between $0$ and $p-1$. It seems that for every $p$ and every $c$ we can find integers $a,b$ such that : $$ a^2 + p b^2 = c \mod p^2 $$ Is ...
mick's user avatar
  • 16.4k
1 vote
0 answers
46 views

Show that for k>0, m>=1, x congruent to 1 (mod m^k): x^m is congruent to 1 (mod m^(k+1) [duplicate]

This question is from Dudley's Elementary Number Theory. "Show that for $k\gt 0$, $m \ge 1$, and $x \equiv 1\ (mod\;m^{k})$ implies $x^{m} \equiv 1\ (mod\;m^{k+1})$." I have come up with an ...
k endres's user avatar
1 vote
0 answers
32 views

How do you parameterize simultaneous solutions to equations with expressions like "$ x +2 \left\lfloor\frac{x}{3}\right\rfloor + 1 - [3 \mid x]$"?

Let all functions be integer functions herein. I.e. $\Bbb{Z}\to\Bbb{Z}$ or $\Bbb{N}\to\Bbb{Z}$ where appropriate. I found this jewel of floor functions. So that made me wonder whether, we can solve ...
SeekingAMathGeekGirlfriend's user avatar
0 votes
0 answers
47 views

The prime race $a_i \mod 11$ vs $b_i \mod 11$ conjecture

Let $f(n,a)$ be the number of primes of type residue $a \mod 11$ between $1$ and $n$. Is it true that for all $n>1$ we have $$f(n,1)+f(n,2)+f(n,3)+f(n,5)+f(n,7)+f(n,6)+f(n,8) > f(n,4)+f(n,9)+f(n,...
mick's user avatar
  • 16.4k
-2 votes
1 answer
103 views

Is there a way to show that the Fibonacci subsequence $F_{6n+2}+2$ can't have any square number? [closed]

I'm investigating the Fibonacci sequence $F_{6n+2}+2$. I searched, by Maple, the first $10000$ numbers. I couldn't find any squares. I tried using quadratic residue and modularity but I got nothing ...
ThePirateKing's user avatar
1 vote
0 answers
30 views

Existence of $n$ where $S_b(n^k) \equiv r \pmod{M}$ where $S_b$ denotes sum of digits in base $b$

Let $b, k, M \in \mathbb{N} \setminus \{1\}$, $r \in \{0, 1, \dots M-1\}$ and $S_b: \mathbb{N}_0 \rightarrow \mathbb{N}_0 $ denote the method which outputs the sum of digits of its input in base $b$. ...
EnEm's user avatar
  • 1,191
1 vote
0 answers
20 views

find the other lines that intersect a set of evenly-spaced points along a line on a torus

i have a square, side length $2\pi$, and i'm drawing lines on it that wrap around when they reach the edges - this is of course equivalent to the surface of a torus. the lines are straight lines that ...
Silver's user avatar
  • 111
2 votes
1 answer
56 views

Solving quadratic modular equations

I am interested in how to solve equations of the form $x^2 \equiv d \mod p$. I did try to read into the topic. In the book I am reading one is introduced to the Legendre-Symbol, then to the Jacobi-...
NTc5's user avatar
  • 609
3 votes
1 answer
53 views

Prove that $2^𝑎 + 3$ is divisible by $2^{𝑎 + 𝑏} − 9$ only if $𝑎 = 𝑏 = 2$

For $a$ and $b$ positive integers, I want to show that $2^𝑎 + 3$ is divisible by $2^{𝑎 + 𝑏} − 9$ only if $𝑎 = 𝑏 = 2$ and no other solutions exist. Note that I am only interested in the case ...
blu potatos's user avatar
1 vote
0 answers
70 views

Primes of the form 2...21

I was wondering what properties could have these numbers: $21, 221, 2221, 22221, ...$ At glance I thought this set would have infinitely many primes. Immediately I went to Python and I realized that ...
Francisco J. Maciel Henning's user avatar
1 vote
1 answer
43 views

Number of solutions to underdetermined system of equations in modular arithmetic vs real or complex valued equations

I just watched this video about solving a video game puzzle using matrices defined over the integers mod 3, which essentially ended up being a lesson about how the usual rule, that square matrices ...
Mikayla Eckel Cifrese's user avatar
2 votes
0 answers
19 views

Simple divisibility question [duplicate]

I want to find all $k$ such that for every pair of positive integers $(m, n)$, $(km + n) \mid{} (kn + m) \implies m \mid{} n$. Here are my ideas so far: Say that $(km + n) \mid{} (kn + m)$. Then ...
Christopher Miller's user avatar
4 votes
0 answers
163 views

Can we efficiently compute $a!\mod b$?

It is well known that we easily can compute , say , $2^a\mod b$ for large integers $a,b$. We can use the repeated square method which gives a fast result even if $a,b$ have , say , $50$ decimal digits....
Peter's user avatar
  • 85.1k
0 votes
0 answers
49 views

Find the reminder of a very large number (power of to the power of to the power of etc) [duplicate]

How would you approach the following problem? I've tried to focus on last digits for example but that didn't lead me to the answer (Like, 2021^(any number) will have last digit 1). Can you guys give ...
Prim3numbah's user avatar
0 votes
0 answers
51 views

MOD of a negative number [duplicate]

-- I checked the other similarly titled questions, they are not duplicates. I was playing around, and noticed that in Excel if I did 5%(-4) (I used function of "=MOD(5,-4)") that the answer ...
Doragon's user avatar
  • 133

1
2 3 4 5
229