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
0answers
10 views

Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and ...
1
vote
1answer
19 views

The order of its elements in the additive group $\mathbb{Z}/9\mathbb{Z}$.

I want to determine the order of each element in the additive group $\mathbb{Z}/9\mathbb{Z}=\lbrace \bar{0},\bar{1},\bar{2},\dots, \bar{8}\rbrace$. It is taken from the Example (4) page 20 in Abstract ...
1
vote
1answer
21 views

If $x$ is a square modulo two primes, then it is a square modulo their product

$a, b$ be integers, $p, q$ primes. If $x \equiv a^2 $ (mod $p$) and $x \equiv b^2$ (mod $q$), then $x \equiv c^2$ (mod $pq$) for some interger $c$. I attempted to use Chinese Remainer Theorem, ...
2
votes
1answer
41 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
0
votes
1answer
54 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
3
votes
1answer
34 views

How to apply modular division correctly? [duplicate]

As described on Wikipedia: $$\frac{a}{b} \bmod{n} = \left((a \bmod{n})(b^{-1} \bmod n)\right) \bmod n$$ When I apply this formula to the case $(1023/3) \bmod 7$: $$\begin{align*} (1023/3) \bmod ...
0
votes
1answer
8 views

Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
1
vote
3answers
59 views

Equation system modulo prime

I have an excercise, it is to solve $$9\equiv_{p}8k_1+k_2$$ $$32\equiv_{p}6k_1+k_2$$ $$45\equiv_{p}11k_1+k_2.$$ $k_2$ is easily eliminated from the equations but I don't know how to proceed from ...
0
votes
1answer
38 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?
1
vote
3answers
35 views

Euler's theorem (modular arithmetic) for non-coprime integers

I am trying to calculate $10^{130} \bmod 48$ but I need to use Euler's theorem in the process. I noticed that 48 and 10 are not coprime so I couldn't directly apply Euler's theorem. I tried breaking ...
0
votes
2answers
23 views

Congruence with additional conditions. [on hold]

Let $$\left(ac \equiv bc \pmod m\right) \wedge \left(gcd(c,m) = d\right) \implies a \equiv b \pmod {\frac{m}{d}} $$ Is it true? Why? Thanks in advance.
0
votes
2answers
51 views

General method to solve a modular system

I noticed that if we got a system of modular equations that all equals to $0$ we can always solve the system; for example in a system like this: $$\begin{cases}n \mod m =0 \\n \mod m' =0 \\n \mod m'' ...
0
votes
2answers
48 views

Smallest integer $x$ for which 10 divides $2^{2013} - x$

Find the smallest integer $x$ for which 10 divides $2^{2013} - x$ Obviously, $x \equiv 2^{2013} \pmod{10}$ But how can I reduce $x$?
0
votes
2answers
35 views

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$ I have not been able to show the above. I would greatly appreciate any help.
1
vote
3answers
37 views

Proving a particular divisibility rule for 7

I came across this rule of divisibility by 7: Let N be a positive integer. Partition N into a collection of 3-digit numbers from the right (d3d2d1, d6d5d4, ...). N is divisible by 7 if, and ...
3
votes
0answers
36 views

Points Distributed evenly around a circle: how many points are in each region?

A circle of circumference $2$ is split into three arcs of length $\frac{2}{3}$ (so the regions are $[0,\frac{2}{3})$, $[ \frac{2}{3},\frac{4}{3})$, $[\frac{4}{3},2)$, $2$ identifies with $0$) and ...
2
votes
1answer
15 views

Modular Arithmetic, Pythagorean triples

I'm not sure if this question should be under Modular Arithmetic, but that's where it was in my book. Show that, if $x$, $y$, and $z$ and integers such that $x^2 + y^2 = z^2$, then at least one of ...
0
votes
2answers
51 views

Find the number which is the sum of different consecutive integers

Problem: Find $n$ such that $n>200$ $n$ can be written like the sum of of $5$, $6$, and $7$ consecutive integers I'm currently studying modular arithmetic so I tried to solve witusoinh it. ...
1
vote
2answers
36 views

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$. The hint says that because $t_1^2+t_2^2+ \cdots +t_n^2 = t_n(3n^3 + 12n^2 + 13n + ...
1
vote
4answers
71 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
1
vote
3answers
33 views

Solve diophantine equation using modular arithemtic

Solve for integers, $x, y$ $4258x+147y=369 \implies 4258x \equiv 369 \pmod{147}$ I got this question from SE, but I want to try this approach. I suppose we will find the inverse modulus of $4258 ...
0
votes
1answer
30 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
27 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
28 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
52 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
49 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
69 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
58 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
28 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 ...
-2
votes
1answer
20 views

Comparing coeficients of modulo arithmetic simultaneous equations [on hold]

Consider set of simultaneous modulo equation, $n> 2$ being prime and $xy \ne 0 \mod n$. $2x +2y=e \mod n$ $ax+by=e \mod n$ How do i show that a=2 and b=2 (mod n for both). is it just clear?
0
votes
1answer
23 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
19 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
34 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
20 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
30 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
29 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
38 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