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

4
votes
2answers
126 views

What's the answer of (10+13) ≡?

As to Modulus operation I only have seen this form: (x + y) mod z ≡ K So I can't understand the question, by the way the answers are : ...
1
vote
1answer
607 views

Modulo of (Power of 2 divided by a number)

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity. Meaning, I basically wanted $(2^a/b) \mod K$. Take an ...
2
votes
1answer
98 views

Name of this division property

Let us take two integers, $a$ and $b$. Let us then take $\lfloor a / b\rfloor = c$ and $a \bmod b = d$. Obviously, it follows that $a = bc + d$. Our professor claimed that this was called the ...
1
vote
3answers
251 views

How many distinct degree 7 polynomials are there over the modular arithmeic modulo 7?

If it's infinite, is it countable or uncountable infinite? I am a newbie to this topic... I don't know what modular arithmetic for polynomials means. Can someone please give me a link where I can ...
6
votes
5answers
316 views

How to solve $100x +19 =0 \pmod{23}$

How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ? In general I want to know how to solve $ax=b \pmod{c}$.
1
vote
0answers
64 views

Modular simple equation

Let's say I have three known numbers : $a$, $b$ and $m$. I want to find the smallest $x$ so that $a.x \equiv b\ (mod\ m)$ (the product of $a$ and $b$ is congruent to $b$ modulo $m$). In the cases ...
13
votes
2answers
452 views

A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems: (a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of ...
0
votes
1answer
101 views

$\mathbb{Z}/n\mathbb{Z}[T]$ and zero divisors

I read the following in wiki, but I can't understand what is meant by "divisor" there. Notice that $(\mathbb{Z}/2\mathbb{Z})[T]/(T^{2}+1)$ is not a field since it admits a zero divisor ...
2
votes
0answers
32 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...
1
vote
1answer
457 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
1
vote
1answer
835 views

How to use Fermat's theorem in congruence problems

Two days ago I asked about how to solve questions of the type: Find last digit of $27^{27^{26}}$. or Find the remainder when $27^{45}$ is divided by $7$, using congruences. I ...
3
votes
1answer
436 views

Calculating the residue of power towers

I want to calculate the residue of a power tower. How do I do that? For example, I want to know the answer to this: $$2 \uparrow\uparrow 10 \pmod{10^9}$$
6
votes
2answers
545 views

Find all linearly dependent subsets of this set of vectors

I have vectors in such form (1 1 1 0 1 0) (0 0 1 0 0 0) (1 0 0 0 0 0) (0 0 0 1 0 0) (1 1 0 0 1 0) (0 0 1 1 0 0) (1 0 1 1 0 0) I need to find all linear ...
5
votes
5answers
240 views

Proving that $2^{2^n} + 5$ is always composite by working modulo $3$

By working modulo 3, prove that $2^{2^n} + 5$ is always composite for every positive integer n. No need for a formal proof by induction, just the basic idea will be great.
3
votes
4answers
114 views

Trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$

I am having trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$, the collection of residue classes having a multiplicative inverse in $(\mathbb Z/n\mathbb Z)$; and apparently, ...
2
votes
2answers
94 views

Counting the number of matrices which cause collision

Let $m,n \in \mathbb{N}$, and $q$ be a prime number. Let $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$ be a matrix. In the following, assume that all additions and multiplications are performed modulo ...
6
votes
2answers
845 views

Legendre symbol, second supplementary law

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how. Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$ n ...
1
vote
1answer
625 views

Modulus Distributing Over Multiplication?

Given positive integers a,b,c and k: Define a function $M: \mathbb{Z^2} \rightarrow \mathbb{Z}$ as $$M(x,y) = (x \bmod y)$$ i.e. the remainder of integer division The following is always true: ...
39
votes
14answers
3k views

'Linux' math program with interactive terminal?

Are there any open source math programs out there that have an interactive terminal and that work on linux? So for example you could enter two matrices and specify an operation such as multiply and ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
1
vote
0answers
181 views

Lucas' theorem Consequence

Lucas' theorem consequence $$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$ $$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$ $$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$ ...
2
votes
2answers
131 views

How many elements $a \in \Bbb{Z}_N$ such that $ax \equiv y \mod N$

Consider the ring $\Bbb{Z}_N$ of arithmetic modulo $N$: $\{0,1,2, \ldots ,N-1\}.$ Given $x,y \in \Bbb{Z}_N,$ how many of the elements of $\Bbb{Z}_N$ when multiplied with $x \pmod{N}$ result in $y$? ...
3
votes
9answers
205 views

If both $a$ and $b$ $\not \equiv 0 \pmod{p}$ then $ab \not\equiv 0 \pmod{p}$

Any help with this proof would be great. Not even sure where to begin. I'm pretty much a total newbie. If $a$ is not congruent to $0 \pmod{p}$ and $b$ is not congruent to $0 \pmod{p},$ where $p$ ...
1
vote
3answers
101 views

How to show that $h(x^p) \equiv h(x)^p \pmod{p}$? [duplicate]

Possible Duplicate: Why $g(x^{p})=(g(x))^{p}$ in the reduction mod $p$? Let $h(x) \in \mathbb{Z}[x]$ and $p$ be a prime. We know that for any integer $\alpha$ we have that $\alpha^p \equiv ...
2
votes
3answers
96 views

The square of every integer is of the form either $3k+1$ or $3k$

How can I prove that square of every integer is of the form either $3k+1$ or $3k$, but not $3k+2$? My approach I considered first, the integer $n$ to be even and then $n= 2m$; and if $n$ is odd ...
2
votes
0answers
257 views

$a^{(b^c)} \mod m$ where $c$ can be very very large

I am trying to solve the following problem. I need to find the value of $$ a^{(b^x)} \bmod m $$ where $a,b$ are integers and $$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
0
votes
1answer
61 views

Confusion in the answers given by mathematica

When I typed in 6^-1 mod 49 in Wolfram|Alpha, it gave me an answer of 41. Link here If I type the same thing as (1/6) mod 49 , I don't see 41 any more. Why is this happening ?Link here A ...
1
vote
1answer
683 views

Solving a polynomial modulo an integer

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
-2
votes
3answers
444 views

$a/b\bmod{m}$ when $m$ is not a prime

I need to find $(a/b) \bmod m$ where $$m= 500000002$$ (hence $$m = 148721 \times 41 \times 41 \times 2\qquad\text{(prime factorization)}$$ basically I need to find $a_n\binom{2n}{n}$, which satisfies ...
0
votes
2answers
104 views

Prove or Disprove $xa \equiv 1 \pmod{ n}$

If $a\in\mathbb{Z}, n\in\mathbb{N}$, then the equation $xa\equiv1\pmod {n}$ has a solution for some $x\in\mathbb{Z}$. I'm not quite sure where to start. I know that $n|(xa-1)$, so $ns=xa-1$ for some ...
1
vote
2answers
201 views

Find the remainder in the following case where there's a infinite power tower of $7$.

What is the remainder when $$7^{7^{7^{7^{.^{.^{.^{\infty}}}}}}}$$ is divided by 13? I'm getting $6$. Is it correct?
2
votes
4answers
86 views

Turn fractions into $\mathbb Z_7$ elements

I had to perform a division between two polinomials $2x^2+3x+4$ and $3x+4$, my book suggests to do this operation without worrying about the modulo. So my result is ...
0
votes
1answer
69 views

System of congruential equations

I read this question about breaking a LCG, but I can't understand how to solve the system of 2 equations given 3 sequential outputs. The system should be ...
1
vote
2answers
102 views

How to solve such congruences? [duplicate]

Possible Duplicate: HCF/LCM problem Given some positive integers $a_i, a_{i+1},\dots,a_n$ we need to find as large as possible number $X$ such that $a_i \pmod x = a_{i+1} \pmod x = \dots = ...
0
votes
2answers
59 views

Security of a particular cryptosystem

I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution ...
2
votes
1answer
470 views

Explain Carmichael's Function To A Novice

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all co-primes less than n. 6 makes sense to ...
4
votes
4answers
665 views

Solve the simultaneous congruences: $2n + 6m\equiv 2 \pmod{10}$ and $n + m\equiv -2 \pmod{10}$

To solve the simultaneous congruences $$2n + 6m\equiv 2 \pmod{10}$$ and $$n + m\equiv -2 \pmod{10}$$ I tried to add the two congruences together so I got: $$3n + 7m\equiv 0 \pmod{10}$$ But I am not ...
2
votes
1answer
188 views

Congruence subgroups and modular curves of type (M,N)

I would like to study the "modular curve" $Y(M,N)$, parametrizing an elliptic curve $E$ together with $p \in E[M]$ and $q \in E[N]$ (here and in the following $M$ divides $N$). Let $\Gamma(M,N)$ be ...
3
votes
2answers
5k views

Congruence Modulo with large exponents

How will the congruence modulo works for large exponents? What theorem/s may be used? For example to show that $7^{82}$ is congruent to $9 \pmod {40}$.
13
votes
5answers
3k views

If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
1
vote
1answer
33 views

Given k % y, how can I adjust the dividend (k) to preserve the modulo when the divisor (y) is incremented by one?

In a programming algorithm, I'm using the result of k % y. I need to understand how to adjust k when the value of y is incremented by one to preserve the same ...
4
votes
5answers
207 views

Property of $2^n+1=xy$

I was wondering if the following were true. It makes sense but I'm having trouble concocting any formal reasoning. Let $2^n+1=xy$ for some integers $x,y>1$ and $n>0$. For $a\in\mathbb{Z}^+$, ...
4
votes
5answers
676 views

Modular Inverses

I'm doing a question that states to find the inverse of $19 \pmod {141}$. So far this is what I have: Since $\gcd(19,141) = 1$, an inverse exists to we can use the Euclidean algorithm to solve for ...
3
votes
4answers
1k views

Modular arithmetic for negative numbers

If I have the congruence $$m^2 \equiv -1 \pmod {2k+1}$$ how do I solve for the solutions to this congruence (given that I know $k$)?
7
votes
1answer
122 views

A proof in number theory dealing with modular congruences.

So we are asked to show that $$(p-1)(p-2)\cdots(p-r)\equiv (-1)^{r}r! \pmod{p}$$ for $r=1,2,...,p-1$. I worked on it and I want to know if my proof suffices to show what is being asked. I would also ...
3
votes
4answers
67 views

How do I prove exchangeable modularity?

How do I prove that, considering all numbers natural, and p and i relatively prime, $mp+n \not \equiv 0 \pmod i$ is the same as $m-x \not \equiv 0 \pmod i$ considering x a natural number and the ...
1
vote
3answers
459 views

Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that ...
10
votes
3answers
1k views

How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$ Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$. How we can find the ...
3
votes
2answers
77 views

Solving for $c$ in $a(b + cd) \equiv 0 \mod e$

If I have a modulo operation like this: $$(a ( b+cd ) ) \equiv 0 \pmod{e},$$ How can I derive $c$ in term of other variables present here. I.e. What function $f$ can be used such that: $$c = f ...
2
votes
0answers
119 views

Determining maximum value of $a^b\bmod N$ when $\gcd(a,b)$ is known

Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$. Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number? We have a finite ...