# Tagged Questions

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

55 views

### How do I find a primitive element in $Z_7$?

I understand the definition of a primitive element. I also know that 3 is primitive element of $Z_7$. I was shown that 2 is not primitive element of $Z_7$ because $2^{3}$ = 8= 1. I do not understand ...
226 views

### Checking the IBAN and dividing large numbers mod 97. Why does it work?

What's the reason (or is there an easy explanation) of why it is possible to calculate the division mod $97$ of a large number by first calculating it for the first $9$ (or $6$?) leftmost digits and ...
97 views

### Number of ways to pick N numbers from 0,1,…,N-1, with possible duplication, with sum equal 0 mod N

We have the numbers $0,1,2,....,N-1$ in $\mathbb Z_N.$ I want to pick $N$ numbers from these. These are the rules: Duplication may occur We don't care about ordering, $00041$ is equivalent to $40010$...
117 views

### Find $7^{1\,000\,000\,000\,000\,000} \bmod{107}$ [duplicate]

What is a shortcut to doing this kind of problem? I know that 7 and 107 are both prime number; thus, I assume that has something to do with the appropriate approach/solution. But beyond that I am ...
98 views

### find a number such that, for all $a$ in $\{0,…,1926\}$, $a^x \equiv a \mod 1926$.

I don't want the answer, but I need some help on how to figure out the answer. If you could point me in the direction of a useful math theorem or technique it would much much appreciated. Also, I am ...
66 views

### Why Are There No Solutions To $2^x \equiv 3\pmod{9}$?

I know this congruence has no solutions because $\gcd(3,9) \ne 1$. I would like to understand why this gcd restriction is needed for solvability. Thanks!
150 views

### Solving equation with mod and one variable

I've marked this up the best way I can: $0 \equiv (19+16x) \pmod{15-x}$ I can repeat this equation filling in $x$, which gets increased by one with each pass. When you get to $x$ = 8, the remainder ...
143 views

### Solving modulus equation systems

I am studying for a test in discrete math and I created my own question but I cannot seem to solve it. Is it possible to solve the following equation system (without brainless testing), and if so, ...
87 views

### If a, b ∈ Z are coprime show that 2a + 3b and 3a + 5b are coprime.

If $a, b \in \mathbb{Z}$ are coprime show that $2a + 3b$ and $3a + 5b$ are coprime. My normal approach seems to get me nowhere.
48 views

### Proving the Divisibility Rule for $3$ [duplicate]

Theorem: If 3 divides the sum of the digits of a number, then 3 divides that number
34 views

### Inverse Modular Arithmetic

or example I have this expression: $x^{11} \mod 41 = 10$ I need to find the value of x, never mind about the process of getting the answer. What I need to know is how do I find the inverse of ...
47 views

### compute $2^{1212}$ mod $2013$

Condition: Using Fermat's Little Theorem We get $2^{2012} \equiv 1$ mod $2013$ Hence $2^{1006} \equiv 1$ mod $2013$ But I can't seem to go further than here...any suggestions?
83 views

### Modular Arithmetic Inverse Exponent Simplification

Need help on where to start here. Given $a^b\mod c = d$, where $b$, $c$ and $d$ is known, how do I find $a$? Thank! I just wrote some arbitrary number here: $x^{13} \mod 47 = 17$, how do I ...
43 views

76 views

78 views

### Solve $x^5 - x = 0$ mod $4$ and mod $5$

I'm trying to solve $$x^5-x=0$$ in $\mathbb{Z/5Z}$ and $\mathbb{Z/4Z}$ I don't see how to proceed, could you tell me how ? Thank you
62 views

### Solve mod equation, how?

Ok so how would I solve for $j$: $(e*j)\bmod z=1$ When $e$ and $z$ are known integers. I am at a loss with this without using trial and improvement. Is there a formula I could use?
63 views

### Multiple of $7$ that has remainder $1,2,3$ divided by $2,3,4$ respectively

I want the multiple of $7$ that has remainder $1,2,3$ divided by $2,3,4$ respectively. Now I have had a search of similar questions, but I may have missed it since I am on a phone. This question ...
65 views

### Finding a power of x to be equivalent to some number in modular arithmetic

I'm struggling to work through how to find $x$ such that $x^{11}\equiv 10\mod42$. It has been previously worked out that $11^{-1}\equiv 15\mod41$, although I'm unsure how this helps. What I've so ...
419 views

27 views

### Show that $T^n(x,y)=\left(x+n\alpha \mod 1, y+nx+\frac{n(n-1)}{2}\alpha \mod 1 \right)$

Let $\mathbb{T}^2=\mathbb{R}^2 / \mathbb{Z}^2$. Let $T: \mathbb{T}^2 \rightarrow \mathbb{T}^2$ be the transformation. Let $\alpha \in \mathbb{R}$. $$T(x,y)=\left(x+\alpha \mod 1, x+y \mod 1 \right)$$...
116 views

### Proof of divisibility using modular arithmetic: $5\mid 6^n - 5n + 4$

Prove that: $$6^n - 5n + 4 \space \text{is divisible by 5 for} \space n\ge1$$ Using Modular arithmetic. Please do not refer to other SE questions, there was one already posted but it was using ...
108 views

### Do we have $-1\bmod 2 \equiv -1$ or $+1$?

As far I can calculate $-1 \bmod 2 \equiv -1$, but the software I am using (R) is telling that $-1 \bmod 2 \equiv +1$. This is the R code: -1%%2 [1]1 Which is ...
87 views

43 views

### $a_1,a_2,\ldots,a_{11}$ and $b_1,b_2,\ldots,b_{11}$ are $2$ permutations of $1,2,\ldots,11$. Show that atleast…

Let $a_1,a_2,\ldots,a_{11}$ and $b_1,b_2,\ldots,b_{11}$ be 2 permutations of $1,2,\ldots,11$. Show that atleast 2 of $a_1b_1,a_2b_2,\ldots,a_{11}b_{11}$ will have same remainder $\mod 11$ My attempt:...
135 views

### pattern in decimal representation of powers of 5

The first few powers of $5$ are given by: \begin{array}{r} 5 \\ 25 \\ 125 \\ 625 \\ 3125 \\ 15625\\ 78125\\ 390625\\ ...
26 views

### If $10^e \equiv 1 \pmod n$ and $\gcd(10, n) \neq 1$ find the period of $\frac{1}{n}$

Consider $n=3$ so we have $\frac{1}{3}$. The period's repeating string of digit(s) is $1$ since $10^3 \equiv 1 \pmod 3$. Now, consider $n = 6$ so we have $\frac{1}{6}$. Then the period of the ...
69 views

### provably secure hash function

I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows: Gen: on input $1^n$, run to obtain ...
30 views

### Are there positive integers $x, y$ and $z$ such that $2^{x} · 3^{4} · 14^{y} = 126^{z}$

Can anyone give me a tip on how to approach this. Possibly a theorem of some sort that allows me to work with powers using modular arithmetic. Thanks for the help.
158 views

### Given dividend and divisor, can we know the length of nonrepeating part and repeating part?

$13/92=0.14\overline{1304347826086956521739}$ In this example, the length of nonrepeating part is $3$. The length of repeating part (repeating period) is $21$. I collected some properties related to ...
253 views

### inverse modulo, modulo arithmetic

I was given following example in the book, however I am not sure how can the result of 27 be calculated. I realise that -13 + 40 gives 27, however how 27 ≡ −13 (mod 40) is the same as 3·(−13) ≡ 1 (mod ...
1k views

### How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
I have understood that $-340$ mod $60$ = $20$ because $-6 \times 60$ = $-360$ is smaller than $-340$. Can someone explain why $-340$ mod $-60$ = -$40$?
### Is $((a \mod n) + (b \mod n) ) = (a + b) \mod n$?
As we know $(a + b) \mod n = ((a\, \bmod\, n) + (b\, \bmod\, n))\, \bmod\, n$ Is their reversal also true like this $((a \mod n) + (b \mod n)) = (a + b) \mod n$. If not then what could be its ...