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

learn more… | top users | synonyms

1
vote
2answers
46 views

Modular exponentiation

How do you solve: $$5^{{9}{^{13}}^{17}} \equiv x\pmod {11}$$ I've been trying with this but no luck. I get to ${{9}{^{13}}^{17}} \equiv x\pmod {11}$ from $5^3 * 5^3 * 5^3 = 64 \equiv 9\pmod {11}$. ...
1
vote
1answer
65 views

Quick methods to check perfect$ 4^{th}$,$ 5^{th}$, $6^{th}$ powers

Are there any quick modulus methods to check if a number could be a perfect power (4, 5, 6)? Preferably binary methods. For example, a perfect fourth power has to be $0, 1 \pmod{16}$ from a square ...
2
votes
4answers
40 views

Finding solutions to $h(j)=15+j^2 \mod 17, j \in \mathbb{N}$

I have a function such as this: $$h(j)=15+j^2 \mod 17, j \in \mathbb{N}$$ When $h(j)=7$ I know that there is a solution to this as: $h(3)=15+(3)^2 \mod{17}=7$ How can I prove that there no solutions ...
3
votes
0answers
71 views

Simplify this number using modular arithmetic.

Find the last 10 digits of the number $9511627776^{195761}2^{17}$. Well, I know I just have to perform $$9511627776^{195761}2^{17} \mod 10^{10}$$ and I know that $195761$ is prime. Also, $9511627776 ...
0
votes
1answer
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 ...
2
votes
1answer
232 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 ...
6
votes
1answer
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$...
0
votes
1answer
118 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 ...
3
votes
3answers
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 ...
3
votes
6answers
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!
1
vote
1answer
152 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 ...
3
votes
4answers
147 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, ...
0
votes
3answers
88 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.
1
vote
0answers
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
0
votes
2answers
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 ...
2
votes
1answer
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?
0
votes
1answer
84 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 ...
0
votes
1answer
44 views

primitive roots $g^a \mod{p}$

$p$ prime, $g$ primitive root $\mod{p}$, $0 \leq a \leq p-2$ Show: $g^a \mod{p}$ is a primitive root $\mod{p}$ $\Leftrightarrow$ gcd($a,p-1) = 1$ Ideas: $g^a \mod{p}$ is a primitive root if $ord(...
2
votes
4answers
82 views

When can I stop checking if $ \varphi(n) $ is equal to some integer - Euler Totient Function

Take the example $ \varphi(n) = 12 $ After I split into factors $(12 \times 1), (6 \times 2), (4 \times 3)$ I know that $ \varphi(13) = 12 $ and $ \varphi(2) = 1 $, hence $ n = 13 \times 2 = 26 $ is ...
0
votes
1answer
61 views

Modulo operation property

If $x =(a+b) \pmod m$ and we know `$(a+b)\pmod n=(a \pmod n+b \pmod n) \pmod n$ Can we write: $b = (x-a \pmod m)%m$ Please correct me if I am wrong.
0
votes
1answer
39 views

Show that if $ n>1 $ then $ 3^{2^{n}} = 1 + q_{n}2^{n+2} $ for some odd integer $q_{n} $

So basically we have to show that: $ 3^{2^{n}} \equiv 1 $ mod $ (q_{n}2^{n+2}) $ for some odd integer $q_{n}$ Using Eulers theorem we can rewrite this question as: Show $ \varphi (q_{n}2^{n+2}) = 2^...
1
vote
0answers
76 views

What is the efficient way to compute ${n \choose r} \mod k$?

We know that $n\choose r $ = $\frac {n-r+1}{r}$$ n\choose r-1$ And we also know that $(a * b) \mod k = ((a\mod k) *(b\mod k)) \mod k$ Fermat's Little theorem $a^{\phi(m)-1} = a^{-1} \mod m$ ...
0
votes
3answers
250 views

Modulus calculation for big numbers

I am having problems with calculating $$x \mod m$$ with $$x = 2^{\displaystyle2^{100,000,000}},\qquad m = 1,500,000,000$$ I already found posts like this one https://stackoverflow.com/questions/...
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,...
1
vote
1answer
643 views

'Distributive' property for a function mod m

What properties must some function $f(n)$ have for it to be the case that: $f(n) = (n + 3) \mod m = (n \mod m) + (3 \mod m)$? Similarly, what if $f(n) = (n + 3) \mod m = (n \mod m + 3)?$ Is this ...
0
votes
1answer
49 views

Using CRT ( or not ) solve the modular system.

Using CRT or not solve the following: $$\begin{cases} x \equiv 19 \mod 49 \\ x \equiv 10 \mod 14 \end{cases} $$ And now, I don't know how to deal with it. Please help me.
2
votes
1answer
37 views

Modular expression and my trying.

Is it a true:? $$\begin{cases} 2x \equiv 2 \mod 5 \\ 3x \equiv 2 \mod 4 \\5x \equiv 2 \mod 6\end{cases}$$ $$2x \equiv 2 \mod 5 \iff x \equiv 1 \mod 5 $$ $$3x \equiv 2 \mod 4 \iff 6x \equiv 4 \mod ...
4
votes
2answers
166 views

I can't use Chinese Remainder Theorem.

I have a problem with: $$\begin{cases} 6x\equiv 2 \mod 8 \\ 5x \equiv 5 \mod 6 \end{cases} $$ I want to use the Chinese Remainder Theorem, but I can't because of the fact $\gcd(8,6) > 1$. How can ...
0
votes
5answers
51 views

System modular equation.

Consider: $$\begin{cases} x\equiv 2 \mod 4 \\ x \equiv 2 \mod 6 \end{cases} $$ And we would like use Chinese remainder theorem but we can't because $\gcd(4,6) > 1$ How can I deal with it.
4
votes
3answers
359 views

Encryption with large mods

I am studying for a cryptography final and I have come across something I can just not figure out. My math background is rather weak. This is related to RSA and concerns itself with raising numbers ...
0
votes
2answers
59 views

Modular equation with $x^2$

For $x \in \mathbb{Z}_{200} $solve this modular equation $$(x-1)(x-2) \equiv 0 \mod 200$$ I don't know how to deal with that $x$ occurs in second power, I mean $x^2$ I am asking for advice.
0
votes
1answer
128 views

How to continue solving? Perfect Cuboid

I am doing research on perfect cuboids, and I'm looking for values $a,b,c$ such that the following is integer, and I'm not sure how to continue this. Any suggestions are appreciated! $PED$ is a very ...
3
votes
2answers
76 views

Proving all sufficiently large integers can be written in the form $ax+by$

Let $a,b \in \mathbb N \setminus \{0,1\}$ such that $\gcd(a,b)=1$ Let $F=\{ax+by \mid (x,y) \in \mathbb N^2\}$ Prove that all integers $\geq (a-1)(b-1)$ are in $F$, but that $(a-1)(b-1)-1\...
1
vote
2answers
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
2
votes
1answer
64 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?
2
votes
2answers
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 ...
1
vote
2answers
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 ...
2
votes
0answers
442 views

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in $p=...
-1
votes
1answer
57 views

Cube roots in $(\mathbb{Z}/p\mathbb{Z})^*$

Let $p,q$ be two odd prime numbers such that $3\mid(p-1)$ and $3\nmid(q-1)$. I need to show that: a) $1$ has $3$ cube roots modulo $p$. b) If $a,b\in(\mathbb{Z}/q\mathbb{Z})^*$ such that $b^3\equiv ...
2
votes
1answer
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) $$...
2
votes
4answers
119 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 ...
3
votes
2answers
109 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 ...
1
vote
1answer
89 views

Field of polynomials mod n?

I have a few questions and i am looking for some clarification. 1) Is it correct that one can define a field $(Z_n, +, X)$ of integers mod $n$, where all the elements are integers $a$ such that $gcd(...
2
votes
2answers
86 views

Proof involving Euler totient function and modular arithmetic

Let $ n = pq$ where $p$ and $q$ are distinct primes, and let $e$ be an integer coprime to $ \varphi (n)$. Explain why there is an integer $d$ such that $ed = 1 $ (mod $ \varphi(n)$). Prove that $b^{...
3
votes
2answers
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:...
15
votes
1answer
138 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\\ ...
0
votes
1answer
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 ...
1
vote
0answers
70 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 ...
3
votes
1answer
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.
8
votes
2answers
159 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 ...