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
1answer
15 views

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$)

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$) I'm having a trouble showing this. I think I need to ...
2
votes
2answers
25 views

Solve diophantine using modulus

Find all pairs of positive integers $(m, n)$ that satisfy, $mn + 3m - 8n = 59$ Using Modular arithmetic. Okay, this is a diophantine equation, where can I begin?
1
vote
0answers
24 views

Solutions $n^2 = -1 \mod (p_n-1)$

Consider the equation $n^2 = -1 \mod (p_n-1)(*)$ where $p_n > n$ and $f(n) = p_n$ is the largest prime that satisfies the equation. $f(n)$ gives $p_n$ assuming there is a solution to the equation ...
1
vote
0answers
49 views

Evaluate $\sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$

Evaluate: $$I = \sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$$ $$I = \sqrt{2^{2006}\cdot (1 + 2^{5} + 2^{8} )} \pmod{17} = 2^{1003} \cdot \sqrt{2^8 + 2^5 + 1} \pmod{17}$$ The answer is $0$ ...
-1
votes
1answer
46 views

Solve $5991x + 289 \equiv 0 \pmod{2014}$

Solve: $$5991x + 289 \equiv 0 \pmod{2014}$$ $$5991x \equiv -289 \equiv 1725 \pmod{2014}$$ I need to find the inverse of $5991$ modulo $2014$. Start with Euclid's algorithm: $$5991 = 2(2014) + ...
2
votes
4answers
63 views

Proving that $x^5 = x \pmod{10}$ for every integer $x$. [duplicate]

Show that $x^5 = x \pmod{10}$ for every integer $x$. How can I approach this? Should I use induction? I am stuck trying to get it in terms of $x+1$. Some feedback would be appreciated.
1
vote
3answers
53 views

How to find inverse Modulo?

Find the inverse modulo, Modulo inverse of $5991 \pmod{2014}$ ? I am aware of the Euclid algorithm, but I am not sure how to apply it here?
0
votes
1answer
23 views

Proving a statement similar to the Fermat's theorem using modular arithmetic.

I have to prove that if m > 1 and not a prime, then $\exists a,b,c \in \mathbb{Z}$ such that $c \not= 0 (\mod m)$, $ac = bc (\mod m)$, but $a \not = b (\mod m)$. I am sorry I don't know how to put ...
0
votes
1answer
21 views

How to use modular arithmetic to find a rule for the divisibility of 13?

I am failing, I managed to read a proof for the number 9, unfortunately I can't seem to have a clear idea of how to do it for 13. I started by decomposing it in terms of 10's... but that's as far as ...
0
votes
0answers
18 views

Equation involving a modulus and variable in an exponent

How would I solve for the first positive non-zero integer value for $x$ in this equation? Equation: $1 \equiv 4^x \pmod{199}$
0
votes
0answers
22 views

How do i show that $a_n + a_{n+r} + a_{n+2r} = 0$ for all n ≥ 0 if and only if $3r$ is divisible by $p^k − 1$?

Let ${a_n}$ $(n ≥ 0)$ be an m-sequence in $Z_p$ of period $p^k − 1$ where p is a prime and $k ≥ 1$. Suppose that r is a natural number with 0 < r < $p^k − 1$. Show that $a_n + a_{n+r} + a_{n+2r} ...
0
votes
0answers
32 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
33 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
29 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
17 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
28 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
26 views

Remainder of division [on hold]

What is the remainder of the division of $10^{100}$ by $7$? What is the remainder of the division of $10^{100}$ by $13$?
2
votes
1answer
35 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
50 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
102 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
82 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
62 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
35 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
12 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
66 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
18 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
45 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
71 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
41 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
66 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
33 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
42 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
325 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
85 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 ...