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

1
vote
1answer
31 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
422 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
86 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
15 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
113 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
41 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
72 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
101 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
101 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
59 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
62 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
99 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 ...
0
votes
4answers
2k 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
44 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 ...
0
votes
0answers
163 views

Show that if $N$ is an odd prime, then there are exactly $\frac{N + 1}{2}$ quadratic residues in the set $\{0, 1, …, N - 1\}$.

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}$. Show that if $N$ is an odd prime, then there are ...
1
vote
3answers
230 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
351 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
58 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
105 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
589 views

How many pairs of integers $(A, B)$ are there in the range $[1,\ldots, N]$, such that $\gcd(A,B) = B$?

I am given a positive integer $N$ ($N\leq 10^9$). How many pairs of integers $(A, B)$ exist in the range $[1,\ldots, N]$ such that $\gcd(A,B) = B$?
4
votes
2answers
152 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
457 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 ...
1
vote
1answer
608 views

Do (a+b)mod n=a'+b' as same as (a+b) mod n= (a'+b') mod n?

The question is:Let n be a fixed postive integer greater than 1.If a mod n= a' and b mod n =b',prove that (a + b) mod n= (a' + b') mod n and (ab) mod n= (a'b') mod n. My answer so far is:From ...
0
votes
1answer
31 views

Simple Proof as part of Merkle-Hellman

I'm implementing a Merkle-Hellman cryptosystem and I have a question about a small detail. In order for it to work, all potential subsets of the super-increasing sequence must have distinct sums. ...
12
votes
6answers
1k views

How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
2
votes
4answers
2k views

Solving a system of equations using modular arithmetic modulo 5

Give the solution to the following system of equations using modular arithmetic modulo 5: $4x + 3y = 0 \pmod{5}$ $2x + y \equiv 3 \pmod{5}$ I multiplied $2x + y \equiv 3 \pmod 5$ by $-2$, ...
2
votes
2answers
81 views

How to prove $n ≡ n_0 + n_1 + \dots +n_k \pmod{b-1}$

I am trying to prove this statement, where $n$ has base $b$ representation, which can be understood easily using this example: In base $10$, mod $9$ of any number can be found by adding up its ...
3
votes
2answers
113 views

How many products of two single digits $x,y$ end in a specific digit $n$ in a given base $b$?

While one can use brute force (i.e. counting a multiplication table) to see that e.g. in base ten there are 27 combinations yielding zero ($0\cdot n, 2n\cdot 5$ and the other way around, counting ...
8
votes
1answer
93 views

Finding the generators of a subgroup of $\mathrm{SL}_2(\mathbb Z)$

I am trying to solve the following problem: Let $T_{ij}(c)\in\mathrm{SL}_2(\mathbb Z)\ (i\neq j)$ be the elementary matrix which represents the elementary row operation of adding the $j$-th row ...
3
votes
2answers
106 views

Eleven test on integers

For this exercise, I need to calculate all possible numbers that satisfy the eleven test. The eleven test is a generalisation of the following: Let $a_1, a_2, a_3$ be numbers. Then it should hold ...
0
votes
0answers
32 views

How quickly can we find a modulated sequence of powers?

How quickly can we find an element of (at least) multiplicative order at least $p$, where $p \in \mathbb{N}$? The complete question is that we start with a number system of $s$ elements; for example ...
4
votes
3answers
350 views

Concepts of Modern Mathematics (Ian Stewart) - 751=7.107+2?

Concepts of Modern Mathematics by Ian Stewart (1995). In Chapter 3 Ian Stewart talks about Short Cuts in the Higher Arithmetics, one section is on modular arithmetics. When talking about the days of ...
0
votes
1answer
53 views

Relation between $a$ and $a^{-1}$ in integer rings about evenness

Could I ask something seemingly simple? Well, let $N$ be a positive odd number (the reason why I set $N$ to be odd is I could actually solve the problem when $N$ is even which is easy) and $a$ is an ...
0
votes
1answer
72 views

Solving quadratic congruence

How to solve congruence $x^2-2 \equiv 0\pmod a$, $x$ and $a$ are integers, and $a$ mustn't be prime? I have found solution when a is prime, but I haven't found solution for general case.
2
votes
1answer
55 views

Finding Similar Sequences

Can we find two sequences: $$\{a (b^0), a (b^1), a (b^2), a (b^3), \dots, a(b^n)\} \bmod p_1$$ $$\{c (d^0), c (d^1), c (d^2), c (d^3), \dots, c(d^n)\} \bmod p_2$$ that differ by only one number? ...
0
votes
1answer
54 views

how $a+_m(b+_mc)=a+_m(b+c)$?

I am trying to show that the set of first m non-negative integers is a group under the composition of addition modulo $m$. I need some help understanding this step - $$a+_m(b+_mc)=a+_m(b+c)$$ It ...
0
votes
1answer
81 views

Find an integer $x$ such that $107 \equiv x \cdot 2005 \, \pmod{1302}$

If I write it out then $107 \equiv x \cdot 2005 \pmod {1302}$ means that $x\cdot2005 = q1302 + 107$, for some $q \in \mathbb{Z}$ (I could replace 2005 with 703 though that doesn't make it any ...
0
votes
1answer
343 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
1
vote
2answers
239 views

Solve the following system of simultaneous congruences:

\begin{gather} 3x\equiv1 \pmod 7 \tag 1\\ 2x\equiv10 \pmod {16} \tag 2\\ 5x\equiv1 \pmod {18} \tag 3 \end{gather} Hi everyone, just a little bit stuck on this one. I think I am close, but I must be ...
3
votes
2answers
104 views

Modulo Problem, Fermat's little theorem

Find the value of the unique integer x satisfying $O \le x \le 17$ for which $$ 4^{1024000000002} \equiv x\pmod{17} $$ I think this is related to Fermat's little theorem. I'm knowledgeable with the ...
0
votes
1answer
29 views

Finding $a \operatorname{mod} cd$, where $c$ and $d$ are primes

Is there a way to calculate $a \operatorname{mod} cd$, without actually calculating $cd$, where $c$ and $d$ are primes, and $cd$ has $12$ digits?
3
votes
2answers
342 views

Taking modulo by product of 2 primes

If we are given a number $n$, and two primes $p_1$ and $p_2$, and we have $a = n$ modulo $p_1$ and $b = n$ modulo $p_2$, can $n$ modulo $p_1p_2$ be evaluated using $a$ and $b$?
4
votes
2answers
73 views

Multiplicative polinomial inverse revisited

As it usually goes with asking questions for a third person... You don't get it right the first time. Question I asked here is as follows: Let $A(x)$ be a polynomial with integer coefficients. Is ...
2
votes
3answers
84 views

Prove that for all odd $n$, there is an $m$ such that $2^m - 1$ is divisible by $n$

I've been trying to solve a problem that reads as such Prove that for all odd positive integers $n$, there exists a positive integer $m$ such that $(2^m) - 1$ is divisible by $n$. Proof by ...
0
votes
2answers
153 views

What is mod(a,b)?

I was reading the AKS Primality Test. AKS. I could not understand the line : $(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$ What is $\mod{(a,b)}$ in it ?
0
votes
2answers
492 views

Polynomials' multiplicative inverse

Let $A(x)$ be a polynomial with integer coefficients. Is there always a polynomial $B(x)$ for which $$A(x)\cdot B(x)\equiv 1\pmod n$$ (for a given integer $n$). If the answer isn't yes, an answer ...
1
vote
1answer
262 views

Repunit Divisibility

We shall define $R(k)$ to be a repunit of length $k$; for example, $R(6) = 111111$. Lemma: Let $n$ be a positive integer and $GCD(10,n) = 1$. Then, there exists a $k$ such that $R(k) \equiv 0$ $ $ $ ...
1
vote
1answer
2k views

find remainder using modulo arithmetic

what is the remainder when $55^{142}$ is divided by 143? Initially I wanted to use Fermat's little theorem but 143 is not prime. Euler's theorem does not seem to work here either as $(55,143)\neq 1$ ...
6
votes
1answer
244 views

Let $F_n$ be a Fibonacci number and $p$ a prime. Verify that for $p \le 61$, if $p\equiv\pm1 \pmod{5}$ then $p\mid F_{p-1}$

Define the Fibonacci entry point of $p$ to be the least integer $n$ such that $p\mid F_n$ So for example, for $p = 3$ - the Fibonacci entry point is $n = 4$ since $F_4 = 3$ and obviously $3\mid 3$. ...
1
vote
1answer
65 views

$(A^x) \mathbin\% p = (A^{x \mathbin\% (p - 1)}) % p$ if $p$ is prime. Is this true when $A$ is a matrix?

$(A^x) \mathbin\% p = (A^{x \mathbin\% (p - 1)}) % p$ if $p$ is prime. Is this property true when $A$ is a matrix? Suppose $$A=\begin{pmatrix} 1 &0 &1\\ 1 &0 &0\\ 0 &1 &0 ...