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
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
58 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
867 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
126 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
271 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
54 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
148 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
97 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
99 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
545 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
211 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
128 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
57 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
52 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
720 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
234 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.
3
votes
1answer
83 views

Values of $\gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $\gcd(a,b)=1$ Then $\gcd (a-b,\frac{a^p-b^p}{a-b}) = 1 $ or $ p $ (gcd should be ...
1
vote
1answer
35 views

Diophantine equations in relation to modular arithmetic

Here are some of the known definitions: $$a \equiv b \pmod m$$ $$a -b =km \Rightarrow a=km+b$$ Now we also have: $$ax = b \pmod m \Rightarrow ax+my=b$$ I'm having a little trouble relating all of ...
1
vote
4answers
553 views

How to show that $10^n - 1$ is divisible by $9$

How can I show that $10^n-1, 10^{n-1}-1,...., 10-1$ are all divisible by 9? I was considering using Euclid's algorithm, but I can't find a way to get that to work.
1
vote
2answers
135 views

Linear equations congruence

I'm having some trouble with the following: Find integers x and y in the set $\{0, 1, 2, 3, 4\}$ such that $$ 2x - 4y \equiv 1 \pmod 5 $$ $$ 3x + y \equiv 2 \pmod 5 $$ Well I'm a little confused on ...
0
votes
1answer
18 views

Set builder modular arithmetic

I have a set C which is defined as: $$ C= \{ (x|x\in \mathbb Z^+) \land ( x \pmod 3 < 2) \} $$ To find such an x, we have: $x = 3n + 1$ But what am I limited to in this case? if $ n=1 $ then ...
0
votes
1answer
125 views

Bases of $\mathbb{F}_p^2$

Let $\mathbb{F}_p$ be a prime field, and let $V=\mathbb{F}_p^2$. Prove: The number of bases of V is equal to the order of the general linear group $GL_2(\mathbb{F}_p)$
1
vote
1answer
44 views

Determining order of matrices in $GL_2(\mathbb{F}_7)$

I need to determine the orders of the following matrices in the group $GL_2(\mathbb{F}_7)$: $$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix} \text{ and } \begin{pmatrix} 2 & 0\\ 0 & 1 ...
0
votes
4answers
77 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
2
votes
2answers
173 views

Solving a system of equation modul0 5

Consider the system of linear equations $$\begin{pmatrix} 6 & -3\\ 2 & 6 \end{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}=\begin{pmatrix} 3\\ 1 \end{pmatrix} $$ a) Solve the system in ...
6
votes
4answers
108 views

Product polynomial in $\mathbb{F}_7$

I need to compute the product polynomial $$(x^3+3x^2+3x+1)(x^4+4x^3+6x^2+4x+1)$$ when the coefficients are regarded as elements of the field $\mathbb{F}_7$. I just want someone to explain to me what ...
1
vote
4answers
60 views

Finding $a^n \bmod b$?

What is a good algorithm for finding the remainder? For example: What would be the algorithm for finding the solution of $103^{45} \bmod 5$?
1
vote
1answer
64 views

A Modular Diophantine Equation

$a = (N \bmod c)\bmod d$ $b = (N \bmod d)\bmod c$ That is $a$ and $c$ is remainder of $N$ when divided by $c$ and $d$ in different order. What can we say about $N$ if $a,b,c,d$ are known and $N ...
2
votes
1answer
127 views

Modular exponentiation WITHOUT modular exponentiation

Given that 719 is prime, find the least positive residue of $11^{721} (mod\ 719)$, without using modular exponentiation. So, I know how to use modular exponentiation and have done it to get the ...
1
vote
4answers
3k views

Simplifying large exponents in modular arithmetic like $1007$ in $4^{1007} \pmod{5}$

How would I rigorously prove that $4^{1007} \pmod{5} = 4$ and $4^{1008} \pmod{5} = 1$? I was simplifying a larger modular arithmetic problem ($2013^{2014} \pmod{5}$) and got it down to $4^{1007} ...
0
votes
1answer
61 views

Multiplication of floating numbers to a modulus

As we all know, the integers follow the following identity : $$(A\cdot B\cdot C) \bmod M = ((A\cdot B) \bmod M\cdot C) \bmod M$$ But it does not work for real numbers having fractional part. For ...
1
vote
3answers
239 views

Show $f(X)=a_nX^n+\cdots+a_1X+a_0$ has degree $n$ modulo $N$, $f(a)\equiv 0$ (mod $N$) then $f(X) \equiv (X-a)g(X) $(mod $N$)

In Niels Lauritzen, Concrete Abstract Algebra, I'm having trouble showing the following: The problem starts out like this: $f(X)=a_nX^n+\cdots+a_1X+a_0, a_i \in \mathbb Z, n \in \mathbb N$ Part ...
4
votes
2answers
369 views

Show that there are exactly two values in $\{0, 1, …, N - 1\}$ satisfying $x^{2} \equiv a \pmod{N}$.

Fix a positive integer $N > 1$. We say that $a$ is a quadratic residue modulo $N$ if there exists $x$ such that $a \equiv x^{2} \pmod{N}$. Let $N$ be an odd prime and $a$ be a non-zero ...
0
votes
2answers
64 views

Solving $ax \equiv b \pmod y$ where $a, b, y$ are known, $b \mid a$, and $y$ prime

I want to find $x$ satisfying $ax \equiv b \pmod y$, provided that: $a,y,b$ are known numbers $b \mid a$ $y$ is not prime.
1
vote
2answers
126 views

Converse of Fermats Little Theorem generalization hold true?

For the generalized form of FLT, assuming m and n are positive integers and p is prime, if $m \equiv n \pmod {p - 1}$ then for every $a$, $a^m \equiv a^n \pmod p$. Is the converse True, such that for ...
4
votes
2answers
158 views

Show that $c = \max(a, b)$ on $\mathbb{Z}_2$ is not a binary operation

Let $*: \mathbb{Z}_2\times\mathbb{Z}_2 \to \mathbb{Z}_2$, be defined as $[a] * [b] = [c]$, where $c = \max\{a, b\}$, for all $[a], [b] \in \mathbb{Z}_2$. Prove that $*$ is not a binary operation on ...
8
votes
1answer
476 views

Prove that $n$ must be prime.

Here is the complete question: Suppose that $n=2^{m}h+1$, where m is an integer and $h$ is an odd positive integer less than $2^{m}$. Suppose that there is an integer $a$ such that ...