# 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,430 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 135
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 ...
• 498
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 ...
• 154
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 ...
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 ...
1 vote
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$ ...
• 1,494
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 ...
• 1,736
1 vote
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
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 ...
1 vote
57 views

• 556
67 views

• 85.1k
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 ...
• 388