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
2answers
28 views

A add/subtract function that rotates numbers from 1 to 12

I'm having difficulty searching for this since I don't know what it's called. I want a function which will add/subtract in a circular fashion from 1 to 12. I could do this with logic operators (if ...
3
votes
1answer
41 views

Proof of: If $a \equiv b \pmod{d}$ and $x \equiv y \pmod{d}$ then $a + x \equiv b + y \pmod{d}$ and $ax \equiv by \pmod{d}$

I am trying to learn mathematics from the beginning, i.e. trying to form a solid foundation and understanding of basic concepts that I should have learned in high school. I am working through Basic ...
2
votes
2answers
141 views

Prove that 8 is the remainder of $5^{336}$ by $23$

I've searched this website and while there are a few questions similar to mine, I couldn't find what I was looking for/a specific method for what I want to do. I want to understand how one would ...
0
votes
1answer
22 views

Question about congruence modulo notation

I am a bit confused about the semantics (or maybe it would be better to call it semiotics) of the congruence modulo. When we are presented with an expression of the form $$ a \equiv b\ (\textrm{mod}\ ...
3
votes
2answers
43 views

Solving an integer equation

Is it true that if: $x$, $y$, $z$ and $t$ are integers such that: $xz + 7yt = 0$ $and$ $yz + xt = 0$, then $x = y = 0$ $or$ $z = t = 0$? Why or why not? Unless I have miscalculations somewhere ...
2
votes
1answer
41 views

Number Theory: Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

I need to find how many incongruent solutions exist to the equation: $x^2 \equiv 1(mod\space m)$. I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number ...
7
votes
1answer
62 views

Find $f_{1}, f_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(f_{1})$ = deg$(f_{2}) = 2$ and deg$(f_{1}+f_{2})=1$

Find $f_{1}, f_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(f_{1})$ = deg$(f_{2}) = 2$ and deg$(f_{1}+f_{2})=1$ Find $g_{1}, g_{2}$ in $\mathbb{Z_{6}}[x]$ such that deg$(g_{1})$ = deg$(g_{2}) = 1$ and ...
3
votes
2answers
66 views

Polynomial ring addition in $\mathbb{Z_{6}}[x]$

I know this is a very simplest question ever. But, I need help with understanding it. So here it goes... Let, $f(x) = \bar{1}+\bar{2}x+\bar{3}x^2$ and $g(x) = \bar{4}+\bar{5}x$ $\in \mathbb{Z_{6}}...
2
votes
1answer
52 views

Find a non zero element $z\in \mathbb Z_{100}$ such that $yz = 0_{R}$ and $zy = 0_{R}$ where $y =\overline{ 14}$

Find a non zero element $z\in \mathbb Z_{100}$ such that $yz = 0_{R}$ and $zy = 0_{R}$ where $y =\overline{ 14}$ For this I have found such an element to be $\overline{50}$ since $\overline{14}*\...
1
vote
1answer
115 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. ...
2
votes
4answers
87 views

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

Let $p$ be prime, $a,b \in \mathbb{Z}$. Prove that: $$(a+b)^p \equiv a^p + b^p\pmod p$$ How to deal with it.
1
vote
1answer
33 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
82 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
32 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
20 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
96 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 \...
1
vote
1answer
524 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
57 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
51 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
1answer
45 views

inversing using Euclid's algorithm

The question is: Find the inverse of 14 mod 37. I don't know how to do, so could someone please explain it? Thanks in advance.
3
votes
4answers
97 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
1k 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
423 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
36 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, but ...
2
votes
1answer
80 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 solution....
0
votes
1answer
88 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
85 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 ...
2
votes
1answer
39 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
88 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
80 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
47 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?
2
votes
3answers
255 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
68 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
55 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
42 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
242 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
55 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
90 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. $$n=...
1
vote
2answers
79 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$ [duplicate]

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
86 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
62 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
112 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
62 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
35 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
55 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
71 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
77 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
113 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
37 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
31 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 ...