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

$a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even

Questions: Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that $a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even. ...
0
votes
4answers
44 views

$(a+b)^p \equiv a^p + b^p (\mod p)$. Proof. [on hold]

Let $p$ be prime, $a,b \in \mathbb{Z}$. Prove that: $$(a+b)^p \equiv a^p + b^p (\mod p)$$ How to deal with it.
1
vote
1answer
21 views

Finding all the solutions of a linear equations

I am trying to find all the solutions to the following equation: $5x \equiv 15\pmod{25}$ Here is what I've done: Find the $\mathrm{gcd}(5,25) = 5$; there will be $5$ solutions. Divide the original ...
0
votes
1answer
42 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
1
vote
1answer
25 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
0
votes
1answer
18 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
1
vote
1answer
30 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
0
votes
1answer
20 views

Finding the Modular Multiplicative Inverse of a large number

I am practicing some modular arithmetic and I am trying to find the multiplicative inverse of a large number. Here is the problem: 345^-1 mod 76408 I'm not sure how to go about solving this problem. ...
-2
votes
2answers
47 views

What is $\sqrt{3}\pmod 2$?

Please explain your answer, thanks. My attempt: It is $\pm 1$ because $(\pm 1)^2\equiv 1\equiv 3\pmod 2$, so $\pm 1\equiv \sqrt{3}$ by taking square roots.
0
votes
2answers
48 views

How to find $\sqrt{3}\pmod 5$?

I was thinking about this but I couldn't solve it. I am trying to find $\sqrt{3}\pmod {10}$. I found that $\sqrt{3}\equiv \pm 1\pmod 2$ but I can't solve $\sqrt{3}\pmod 5$. Thanks
2
votes
4answers
80 views

How do I prove that if $p$ is prime then $p$ divides $2^{p}-2$?

I know that if $p$ divides $2^{p}-2$ can be written as $2^p - 2 \equiv 0 \bmod p$, but then I get stuck. Im not sure how to take an approach on this.
1
vote
0answers
18 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
30 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
26 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
52 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
56 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
37 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 ...
1
vote
1answer
10 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?
0
votes
2answers
53 views

Show that there exists no integer $x$ such that $3x$ is congruent to 5 (modulo 6)

So far my approach was to rewrite the congruency to $5-3x=6t$ for some integer $t$. My problem is I get stuck in trying to show how $5-3x$ is never divisible by $6$.
1
vote
3answers
60 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
24 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
52 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
39 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 ...
2
votes
1answer
16 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
73 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
32 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
29 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
70 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
29 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
21 views

Comparing coeficients of modulo arithmetic simultaneous equations [closed]

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