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
32 views

Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters. Now, I want to choose an integration step such that my step will land on each of the ...
0
votes
2answers
227 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
0answers
336 views

Calculating Pisano periods for any integer

I recently stumbled across this SPOJ question: http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the Pisano period of a number. After I researched my way through the web, I found ...
1
vote
3answers
84 views

Remainder when dividing $3^{10}+3^{10^2}+3^{10^3}+…+3^{10^{100}}$ by $7$

Determine the remainder of dividing $10^{10}+10^{10^2}+10^{10^3}+...+10^{10^{100}}$ by $7$ We have $10\equiv3\pmod7$ then ...
2
votes
1answer
253 views

How to prove algorithm for solving a square congruence when p ≡ 5 (mod 8)

I'm having trouble understanding why this algorithm works and where it comes from: "Suppose p ≡ 5 (mod 8) is a prime and y is a square (mod p); that is, for some $ x, x^2 ≡ y\ (mod\ p)$. This can be ...
4
votes
0answers
257 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a ...
2
votes
1answer
234 views

Subgroups of $U(n)$ isomorphic to a direct sum of cyclic groups

Let $U(n)$ to be the set of all positive integers less then $n$ and relatively prime to $n$. Then $U(n)$ is a group under multiplication modulo $n$. A. Find integer $n$ such that $U(n)$ contains ...
4
votes
1answer
198 views

Proving that there are n Equivalence Classes Modulo n

For $a,b,n \in \mathbb{Z}$ and $n \geq 2$, I want to prove that there are $n$ equivalence classes mod $n$. I'm not sure how to do it - would I do it inductively? Any help would be appreciated.
9
votes
4answers
1k views

Why is n mod 0 undefined?

I tried to find out what $n$ mod $0$ is, for some $n\in \mathbb{Z}$. Apparently it is an undefined operation - why?
2
votes
1answer
150 views

General Exponential modular equation

Can anyone tell me how to solve this equation for lowest $x$ $$a^x \equiv n \mod m$$ other than trying every possible $x$ from $0$ to $m-1$ ($m$ is prime)?
3
votes
2answers
123 views

Proving divisibility without an inductive proof.

Is there a way to prove that $$10^{n+1} + 10^n + 1$$ is divisible by three without using a proof by induction? We are supposed to use the properties of expressions such as $a$ is congruent to $b \pmod ...
1
vote
2answers
154 views

Extended euclidean algorithm

So I am trying to figure this out. And for one of the problem the question is x*41= 1 (mod 99) And the answer lists ...
0
votes
1answer
32 views

For what $x$ is $\sum_{k=1}^{n-1} (x+k)^n \equiv 0 \pmod n$ dependend on $n$? (so far only *odd* n)

(This is a detail in my attempted answer of this MSE question) We look at $$f_n(x) = \sum_{k=1}^{n-1} (x+k)^n $$ I came to the following observation - for odd $n$ at the moment -, but do not see how ...
0
votes
1answer
26 views

Figuring out a factor of modulo multiplication knowing other factors

So the problem is this - we have a simple equation: (A * B) % N = X All numbers are large integers. We know B, N and X, is it possible for us to figure out the last factor A without checking every ...
3
votes
1answer
33 views

Let $n = 10k + d$ where $d$ is the last digit of $n$. Show that $23|n$ if and only if $23|(2d-3k)$.

This is an exercise on my text book that i don't know how to prove it. Let $n = 10k + d$ where $d$ is the last digit of $n$. Show that $23|n$ if and only if $23|(2d-3k)$.
0
votes
4answers
123 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
2
votes
1answer
196 views

Solving modular equations of two variables

$$7x + 9y \equiv 0 \pmod {31}$$ $$2x - 5y \equiv 2 \pmod {31}$$ I'm supposed to find the x, but I'm stuck in the middle. First I tried to get rid of y. $$53x \equiv 18 \pmod {31}$$ Here now I ...
1
vote
1answer
59 views

Implications of solubility of equations modulo all natural numbers

Let $P(x_1,x_2,...,x_n)=0$ be a given polynomial Diophantine equation in $n$ variables with integer coefficients (for example $x_1^2+3x_2-10+x_1x_2^4=0$). Suppose further that this equation has a ...
1
vote
2answers
323 views

Remainder when $26^{3008} + 3008^{26}$ is divided by $4$

I want to find the Remainder when $26^{3008} + 3008^{26}$ is divided by $4$. What should I do? Even though I've included the tag modular arithmetic I've very limited knowledge about it. How should I ...
0
votes
1answer
18 views

Modular Rules& Arthimetic

If $x=3 \mod 11$ and $x=3 \mod 19$ is there a modular formula/rule that can combine both statements together? If $x=5 \mod 9$ is there a modular formula/rule that can convert $x=5 \mod 9$ into $x=r ...
0
votes
1answer
50 views

systems of modulo equations not relatively prime

How would I go about finding a solution to the following system? $x\equiv 1\text{ mod }12\ \ \ \ \ \ \text{(1)}\\x\equiv4\text{ mod }21\ \ \ \ \ \ \text{(2)}\\x\equiv18\text{ mod } 35\ \ \ \ ...
2
votes
2answers
72 views

Solution to linear congruences

This document states the following theorem: Let $m>1$, $a$ and $b$ be integers. Then $ax \equiv b \pmod m$ has a solution if and only if $gcd(a, m)$ divides $b$. I thought $ax \equiv b \pmod ...
0
votes
2answers
38 views

Mod of set is closed

$\{1,4,7,13\}$ under multiplication $\mod {15}$ is closed under the given operation? I know it's closed. Is there a rigorous way to show it?
2
votes
2answers
51 views

Modular exponentiation problem

$10^7 \pmod {77}$ I tried repeated squaring, which worked but took many computations. I also tried Fermat's little theorem, but since $7 < 77$ I didn't know how to use it. Any simpler way to do ...
3
votes
1answer
114 views

Natural Representation of Factor Group $G/H$

Let $G$ be the positive reals under multiplication and let $H$ be numbers $2^i$ where $i \in \mathbb{Z}$. a) Show H is a subgroup of G b) Show H is a normal subgroup of G Those two are no problem, ...
4
votes
1answer
609 views

An isomorphism that takes Z12 (integers modulo 12 under addition) to Z13* (integers modulo 13 under multiplication)

I'm having a hard time finding an isomorphism that takes the integers in $\mathbb{Z}_{12}$ (those integers modulo 12 under addition) to the integers in $\mathbb{Z}_{13}^{*}$ (those integers modulo 13 ...
1
vote
1answer
65 views

Simple question about modulus property

How come $$4x \equiv 4 \pmod 8 \Longrightarrow x \equiv 1 \pmod 2$$ Also, is there more than one solution to the Chinese Remainder Theorem? I keep getting different answers on e-calculators.
1
vote
1answer
32 views

how comes $s=4$ and $t=3$ for $4=7s-8t$

i am given these two problems: $x\equiv 1 (\bmod 7 )$ and $x \equiv 5( \bmod 18)$ I tried this way: $x\equiv 1 (\bmod 7 )$ is basically $x = 1 + 7s$ and $x\equiv 5 (\bmod 18 )$ is $x=5+18t$ then ...
0
votes
2answers
34 views

Inverses of Modulo N

It's easy to show that relatively prime numbers have inverse mod n via the Euclidian Algorithm-How do you show that they don't necessarily have an inverse if they aren't relatively prime? I would ...
3
votes
2answers
118 views

Why modular arithmetic in secret sharing?

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a ...
6
votes
2answers
96 views

For what $n$ does $x^n \equiv 2\pmod{13}$ have a solution? [closed]

I want to ask for what values of $n$ the congruence $$x^n \equiv 2 \pmod{13}$$ has a solution for $x$.
1
vote
3answers
1k views

Which of the following are complete residue systems modulo 11?

Which of the following are complete residue systems modulo 11? (a) 0,1,2,4,8,16,32,64,128,256,512 (b)1,3,5,7,9,11,13,15,17,19,21 (c)2,4,6,8,10,12,14,16,17,20,22 (d)-5,-4,-3,-2,-1,0,1,2,3,4,5 I have ...
1
vote
1answer
37 views

modular arthimetic equations. is there a different way to do this?

The problem states: When a group is marching 4 people abreast, there is one left over. When they march 5 abreast, there is 2 left over. When they march 7 abreast, there is 3 left. How many are ...
1
vote
1answer
101 views

Why is there no indefinite integral for $\int x\mod{n}$ (where n can be any number)?

Typing integrate x mod 1 in Wolfram|Alpha tells me that "there is no result found in terms of mathematical functions". Why is there no indefinite integral? Couldn't ...
0
votes
1answer
43 views

Modular Arithmetic calculation [duplicate]

(a) x+40 ≡ 1 (mod 99). (b) x ∗ 40 ≡ 1 (mod 99) Is the answer for a x = -39 mod 99 and b x=1/40 mod 99? I believe I am doing it correctly.
0
votes
1answer
183 views

Solving modular arithmetic questions

I am having trouble finding mod arithmetic questions. Can you show how to solve these? $x + 30 \equiv 1 \pmod {12}$ $30x \equiv 1 \pmod {12}$ $x + 3y \equiv 1 \pmod {12}$ and $2x + y \equiv 7 ...
0
votes
1answer
61 views

Modular Arithmetic Question mod [duplicate]

I am having problems solving two-variable mod equations. How would one solve this? $$ \left\{\begin{aligned} x + 3y &\equiv 1 \pmod{11} \\ 2x + y &\equiv 7 \pmod{11} \end{aligned}\right. $$
-2
votes
1answer
39 views

Examples of methods for solving modular equations

Simple mod questions. Can you show example to do such things? $x+40 \equiv 1 \pmod{88}$. $x \cdot 40 \equiv 1 \pmod{88}$. $5a+3b \equiv 1 \pmod{11}$ and $2a+b \equiv 7 \pmod{11}$. Thank you.
1
vote
2answers
50 views

How can I solve these Modular problems?

Very basic question, but how can I solve this? $7x+9y \equiv 0 \bmod 31$ and $2x-5y \equiv 2 \bmod 31$.
0
votes
2answers
105 views

How does one simplify exponents for complex primitive nth roots of unity?

Let us define a complex primitive N-th root of unity, omega: $$ \omega = \cos(\theta) + i\sin(\theta) \\ = e^{\frac{2\pi}{N}} $$ By the definition of an nth root of unity, ω is the second solution to ...
3
votes
3answers
214 views

Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$

Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$. I know I have to use Fermat's Little Theorem for this but I am unsure how to do this problem.
2
votes
2answers
80 views

Number theory proof from AoPS

http://www.artofproblemsolving.com/Resources/articles.php?page=htw.readers In the above link, he gives a problem, namely Let $S(n)$ be the sum of the digits of $n$. Find ...
0
votes
2answers
92 views

difference between mod 7 and (mod 7)

So, I am studying modular division right now, and I want to clarify one thing. $a = b \mod m$ and $a = b \pmod m$ Is the top one $b = mk + a$ ($k$ is an integer) and the bottom one is $a = mk + ...
1
vote
3answers
493 views

Approaching modular arithmetic problems

I'm a little stumbled on two questions. How do I approach a problem like $x*41 \equiv 1 \pmod{99}$. And given $2$ modulo, $7x+9y \equiv 0 \pmod{31}$ and $2x−5y \equiv 2 \pmod{31}$ (solve for $x$ ...
3
votes
2answers
161 views

Modular Multiplicative Inverse when multiplier greater than mod?

I'm having some trouble with this discrete math problem. I'm given this equation: $7x + 9y \equiv 0 \bmod 31$ and $2x -5y \equiv 2 \bmod 31$ And I've solved like I did my other one (which turned out ...
3
votes
2answers
125 views

Properties of $x$ that make $x^2 \equiv x+1 \mod p$, where $p$ is prime

Excuse me for putting in a pinch of computer science. For a pre-calculated prime $p$, I need to find all natural $x$ that make $x^2 = x+1 \mod p$. The problem is that trying thoroughly every $x < ...
0
votes
1answer
55 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
0
votes
1answer
47 views

A proof of existence

I need help proving the following result. Let $p$ be a positive prime number $\geq 5$, $x$ a non zero integer and $y$ a non zero positive integer such that $x^2-y^p=1$ I've successfully proved that ...
1
vote
2answers
546 views

Solving linear congruences with Fermat's theorem and Euler's theorem

Use Fermat's Theorem to solve $18X \equiv 23 \pmod{37}$ Use Euler's Theorem to solve $7X \equiv 39 \pmod{54}$ I don't see how these theorems would work in these instances
0
votes
1answer
187 views

For odd primes $p$, $n^{2p-1}\equiv n\pmod{2p}$

Prove or disprove: If $p$ is an odd prime, then $n^{2p-1}\equiv n\pmod{2p}$. I feel like there would be two cases, for when $n$ is odd and when $n$ is even but I'm not sure.