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

2
votes
1answer
66 views

Computing $\frac{n^2(n + 1)}2 \bmod m$

How to calculate $$\frac{n^2(n + 1)}2 \bmod m$$ where $1 \leq n \leq 10^{16}$ and $1 \leq m \leq 10^7$? Here $m$ and $n$ are integers. What I have done: if n is even: $$\frac{n^2(n + 1)}2 \bmod m = ...
1
vote
1answer
66 views

Can someone verify this direct modulus proof?

This is from Discrete Mathematics and its applications To do this proof, I used this mod property Here is my work What I did was basically expand both sides of (a-c) mod m and (b - d) mod m ...
2
votes
2answers
79 views

Is $1 - 2x$ invertible $\in \mathbb{Z}[x]$?

Let $1-2x \in \mathbb{Z}[x] \subset \mathbb{Z}[[x]]$? Is $1 - 2x$ invertible $\in \mathbb{Z}[x]$? Is $\bar{1} - \bar{2}x$ invertible $\in \mathbb{Z}_{4}[x]$? true/false: $1-2x \in ...
1
vote
1answer
44 views

Natural numbers raised to phi function

Let $a$ and $b$ be relatively prime natural numbers greater than or equal to 2. Prove that $a^{\phi(b)} + b^{\phi(a)} = 1 \quad \pmod {ab}$. The only equations I know with $\phi$ are $a^{\phi(m)} = ...
2
votes
1answer
82 views

When is $(p - 2)! \equiv 1 (\bmod p)$

I want to show when the following is true for $p$ a prime number. $(p - 2)! \equiv 1 \pmod p$. Could someone help me prove this? It worked for $p = 2$, $p = 3$, $p = 5$, so I believe it may work for ...
1
vote
3answers
50 views

Show that if $\gcd(x,y)=1$ then given integers $a,b$ there is an $m$ such that two congruences are satisfied

If $x, y$ are coprime, then for any integer $a,b$ there is an integer $m$ such that: $m \equiv a \;(\bmod\; x)$ $m \equiv b \;(\bmod\; y)$ I approached it like this: Since they are coprime then ...
0
votes
2answers
35 views

Demostrating that a number x is the smallest such that 24x mod (59) = 2 mod (59)

I have to find a number x such that x is the smallest natural number that satisfies this equation: $24x (\mod 59) = 2(\mod59)$. Using Fermat's little theorem and Euler's primes function, given that ...
1
vote
1answer
43 views

Solve using Fermat Theorem

$x^{86} ≡ 6 $ (mod 29) I have the solution but don't understand it. Can someone write step by step instructions on how to do this type of questions. See Question 1(b) for solution: ...
0
votes
1answer
84 views

Solving Linear Equations in Congruence Classes

Okay so I'm having difficulty figuring out something specifically, I'm currently working on congruence classes, now the teacher gave us an example of : $[6]\cdot x=[14]$ in ...
0
votes
2answers
107 views

The multiplication of two even numbers gives an even number

I am given the following proposition: If $m$ and $n$ are even integers, then $mn$ is also an even integer. This is my strategy: An integer $m$ is said to be even if it is divisible by 2 (integer). ...
0
votes
2answers
83 views

Pythagorean Triple divisible by $5$

Show that, if x, y and z are integers such that $x^2+y^2 = z^2$,then at least one of $x,y,z$ is divisible by $5$. I was able to show that at least one of $x$ or $y$ is divisible by $2$. Can someone ...
2
votes
1answer
122 views

Putnam A4 2010, proving an expression is not prime.

Prove that each positive integer $n$: $ x = \displaystyle 10^{10^{10^n}}+10^{10^n}+10^n-1 $ is not prime. This seems like a very difficult problem, any ideas at all? I would like to use modular ...
0
votes
1answer
178 views

Find the remainder when $5^{2001} + (27)!$ is divided by 8

$5^{2001} + (27)!$ is divided by 8. Could someone please help me solve this. I managed to show that $5^{2001} \equiv 13(mod8)$ but now I am stuck and don't know what to do to show the remainder when ...
2
votes
2answers
65 views

Finding Smallest x and y to Satisfy Equation

Find the smallest natural numbers $x$ and $y$ such that $$7^2x=5^3y$$ I'm unsure how to proceed with this question. Could someone explain the process for determining the answer? Added from the ...
6
votes
2answers
96 views

Modularity and prime number sequence

I tried to solve this modular equation involving first $n$ prime numbers. And it is: $$2^{3+5+7+11+13+.....+p_{n-3}+p_{n-2}}\equiv p_{n-1}\ \left(\text{mod }p_{n}\right),$$ where $p_{n}$ is the ...
0
votes
0answers
37 views

Modular Division and Factorial

I am unfamiliar with number theory but am trying to calculate the following for a coding challenge: $$\frac{(N-M-1)!}{N!(M-1)!}\pmod{Q}$$ where $Q$ is prime. I know that I can calculate the ...
0
votes
2answers
25 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
40 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
138 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
20 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
61 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 ...
2
votes
1answer
51 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 ...
1
vote
1answer
101 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
83 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
28 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
72 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
19 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
82 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
349 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
54 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
50 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
41 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
96 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
782 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
278 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
35 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
72 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
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
65 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
33 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
85 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
78 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
42 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
179 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
66 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
52 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$?