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

0
votes
0answers
35 views

Question about galois imaginary and modular arithmetic

Let $p$ be a prime of type $3\space mod \space 4$. Then there is no solution $x^2 = -1 \space mod \space p$. Therefore we can define the so-called Galois imaginary $i$. ( $i^2 = -1 \space mod \space ...
1
vote
2answers
37 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
31 views

Quick methods to check perfect 4th, 5th, 6th 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 8$ from a square ...
2
votes
4answers
34 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
60 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
0answers
23 views

Can someone give me an example of an M-Sequence please?

A sequence ${a_n}$ $(n\geq 0)$ of elements of $Z_p$ is said to be an m-sequence associated with $f$ if it satisfies the mod p linear recurrence relation; $$f_0{a_n} +f_1{a_{n+1}} ...
0
votes
1answer
33 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 ...
-1
votes
1answer
30 views

Remainder of division [closed]

What is the remainder of the division of $10^{100}$ by $7$? What is the remainder of the division of $10^{100}$ by $13$? I have learnt Euler Theorem, and I think it will be useful for this ...
2
votes
1answer
39 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
58 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 ...
1
vote
1answer
106 views

Find $7^{1\,000\,000\,000\,000\,000} \bmod{107}$

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
89 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
64 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
36 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
53 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
0answers
13 views

Modulo operation in combing two array to calculate suffix and prefix

The above Figure Show my two array, Now i am combing my array into one now i have to recalculate prefixes and suffixes. ...
0
votes
3answers
68 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
38 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
19 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
39 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
46 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
9 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 ...
3
votes
4answers
72 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
42 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
32 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}) = ...
0
votes
0answers
46 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
71 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 ...
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, ...
1
vote
1answer
34 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
25 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
33 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 ...
1
vote
2answers
44 views

Chinese Remainder Theorem.

I have a problem with: $$\begin{cases} 6x\equiv 2 \mod 8 \\ 5x \equiv 5 \mod 6 \end{cases} $$ And I want use Chinese Remainder Theorem but I can't because of the fact $\gcd(8,6) > 1$ How can I ...
0
votes
5answers
43 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.
3
votes
3answers
328 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
37 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
86 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 ...
0
votes
0answers
30 views

Modulus property

I Have an array of element , I want to check no. of sub array dividable by 3. Let Array be 1 3 4 5 7 8 After modulus by 3 my array(summing the elements also ) ...
0
votes
1answer
35 views

Modular Arithmetic revision question

I am stuck with some revision. I know this question has been asked but I still don't understand and I can't comment on it. Firstly I must calculate $11^{-1} \pmod {40}$ which I believe to be 11. ...
3
votes
2answers
65 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 ...
1
vote
2answers
75 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
1
vote
1answer
30 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?
0
votes
0answers
8 views

Show that if $O_m(a)=h$ for all $k\ge 1 $ $O_m(a^k)=\frac{h} {(h, k)} $

let $j\ge 1 $. I can show $(a^k) ^j=(mod m) iff \frac{h} {(h, k)} \quad divides \quad j $ but i dont know how to continue from here
-1
votes
0answers
20 views

$x^3 \equiv x+1 \pmod n$ modular arithmetic problem [duplicate]

For all $n \ge 1$ , Let $\psi(n)=\{0\le x<n \mid x^3 \equiv x+1 \pmod n\}$ be the number of elements in the group. For example, $\psi(5) =1$ because the only solution $0\le x \lt 5$ for $x^3 ...
2
votes
2answers
49 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 ...
-5
votes
1answer
69 views

group size of $x^3 \equiv x+1 \pmod n$ [closed]

$\forall 1\le n \;, \psi(n)$is the size of the set $\{0 \le x \lt n \mid x^3 \equiv x+1 \pmod n \}$ prove: let $n \ge 1$ if $gcd(n,6)\gt 1$ then $\psi(n)=0$ any ideas how to approach to question?
1
vote
2answers
51 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
64 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 ...
-1
votes
1answer
46 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
15 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) ...
3
votes
4answers
65 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 ...