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$.
11,429
questions
0
votes
0
answers
23
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 ...
0
votes
0
answers
10
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 ...
- 1
6
votes
1
answer
201
views
Is $(a+b)^n -(a^n+b^n)$ ever divisible by $n^2$? [closed]
More specifically, for any prime $n \neq 2$ are there any integers $a,b$ such that $(a+b)^n -(a^n+b^n)$ is divisible by $n^2$?
All the solutions I've found so far suggest that either $a$, $b$ or $a+b$ ...
- 390
1
vote
1
answer
60
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$ ...
- 1,494
2
votes
2
answers
96
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 ...
- 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 ...
- 883
-1
votes
0
answers
38
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 ...
- 9
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 & = &...
- 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$ ...
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 \...
- 556
0
votes
1
answer
66
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+...
- 315
-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 ...
0
votes
0
answers
30
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 ...
- 5,239
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 ...
- 23
-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 ...
