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
3answers
147 views

Why is the group of units mod 8 isomorpic to the Klein 4 group?

I recently learned that $U_8\cong \mathbb Z/2\mathbb Z\oplus \mathbb Z/2\mathbb Z$. I can see, through a bit of computation, that this is the case, but I was wondering if this is just a coincidence ...
1
vote
3answers
174 views

Computing an inverse modulo $25$

Supposed we wish to compute $11^{-1}$ mod $25$. Using the extended Euclid algorithm, we find that $15 \cdot 25 - 34 \cdot 11 =1$. Reducing both sides modulo $25$, we have $-34 \cdot 11 \equiv 1$ mod ...
0
votes
1answer
223 views

Is a congruence (equivalence) class modulo n a group?

I know that the set of all equivalence classes Z/nZ is a group (with identity element the equivalence class [0], inverse element -[a]=[n-a]=[-a], etc.). However, is a single equivalence class modulo ...
4
votes
1answer
264 views

Fast way to find the smallest root $\mod M$ of a polynomial

Suppose you're given a polynomial of degree $d$ with integer coefficients: $$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$ Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite ...
1
vote
2answers
46 views

Linear congruences $2X\equiv9\pmod{26},\pmod{25}$

May double that of a natural number let rest $9$ when divided by $26$? And when divided by $25$? I tried: $$2X\equiv9\pmod{26}$$ As $(26,2)=2$ and $2\nmid9$ then the congruence linear not ...
5
votes
1answer
64 views

Is it true that if $n$ is even then $\sum_{k=1}^{n}(n \bmod k)<\frac{8}{45}n^2$?

Let $f(n,k)$ be the least non-negative integer such that $n\equiv f(n,k) \bmod k.$ $f(10,k)(k=1,2,\cdots,10)=0, 0, 1, 2, 0, 4, 3, 2, 1, 0.$ Hence $$\sum_{k=1}^{10}f(10,k)=1+2+4+3+2+1=13.$$ ...
2
votes
1answer
64 views

How to solve the equation $x^2=a\bmod p^2$

What is the standard approach to solve $x^2=a\bmod p^2$ or more general $x^n = a\bmod p^n$ ?
0
votes
1answer
33 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
239 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
497 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
87 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
339 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 ...
5
votes
0answers
314 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
280 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
279 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.
12
votes
4answers
3k 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
197 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
154 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
170 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
34 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
28 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
34 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)$.
1
vote
4answers
132 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
323 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
63 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
391 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 ...
6
votes
3answers
457 views

$1^n +2^n + \cdots +(p-1)^n \mod p =$?

Calculate for every positive integer $n$ and for every prime $p$ the expression $$1^n +2^n + \cdots +(p-1)^n \mod p$$ I need your help for this. I don't know what to do, but I'll show you what I ...
0
votes
1answer
19 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
75 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
73 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
47 views

Show that $\{1, 4, 7, 13\}$ is closed under multiplication $\bmod 15$.

How do I show that $\{1,4,7,13\}$ is closed under multiplication $\mod {15}$? I know it's closed. Is there a rigorous way to show it?
2
votes
2answers
57 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
130 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
864 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
72 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
33 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
38 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
154 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
100 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
4answers
2k 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
42 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
125 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
46 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
268 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
66 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
49 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
53 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
147 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
232 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
96 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 ...