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
2answers
40 views

Why 3 is a multiplicative inverse of 7 in modular arithmetic?

why is 3 a multiplicative inverse of 7 in modular arithmetic of 5 ? I'm not able to understand how this is true. PS: I know 3*7-1 % 5 = 0. I'm not able to make sense of inverses in modular ...
2
votes
0answers
48 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
0
votes
0answers
16 views

Intersections of moduli

How do you find "intersection"s of moduli? For example what is the fastest way to find a number $n$ based on modular properties of $n$? Ex: Find is the first number $n$ such that: $n \equiv 2 \mod ...
0
votes
0answers
36 views

What is the remainder of this big number without doing major calculations?

I am solving a problem and came across a situation where to calculate remainder for big values with out doing major calculation. In my case I need to compute the expression: $$2^{n}-1+k ...
0
votes
1answer
27 views

Prove $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism.

I'm working on proving the following claim: "Let $r \in U(n)$ and $\forall s \in \mathbb{Z_n}$, $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism." ...
2
votes
3answers
51 views

What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
0
votes
1answer
35 views

Modulo Quadratic Polynomials

Can you, given a large number N, find a, b, c such that ax^2 + bx + c = 0 has at least N roots? All of this is in any mod you choose.
0
votes
4answers
54 views

Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.
0
votes
3answers
32 views

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$. I tried saying since $n \equiv 2 \pmod 7$, then $7 \mid n - 2$. Thus $7 \mid -5( n - 2)$ or $7 \mid -5n + 10$ and $-5n \equiv 10 \pmod ...
7
votes
1answer
102 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
39
votes
4answers
2k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
0
votes
0answers
47 views
+50

congruence relation between 2 primes and possible equivalent relation in polynomial ring over $GF(2)$

Let $p, q$ be primes. Then linear congruence equation, $ap \equiv r(\mod q)$ can be solved for $a$ and will have unique solution for each value of $r$ such that $a < q$. Is this right ...
1
vote
2answers
41 views

Show that if $a^h ≡ 1\mod p$ then $ a^{ph} ≡ 1 \ \mod p^2$.

I don't know how to proceed. I know that regardless of what h is, it divides the order of a modulo $p$. I also know that the order of a divides $\phi(p) \ \text{mod} \ p$, where $\phi$ is Euler's ...
0
votes
3answers
39 views

x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences?

Say, x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences? I am worried this question is too easy to be true. That is why I am confused. ...
1
vote
4answers
50 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
0
votes
1answer
42 views

Congruence and percentage

Suppose I have three statements of congruence: x = a mod n, y = b mod m, z = c mod p; Furthermore, x is a given percent of x + y + z, as is y and z. Does this uniquely determine x, y, z? Or does it ...
0
votes
3answers
33 views

Proof for a non-conditional statement

I'm having a bit of trouble doing this proof. If $a\in\mathbb{Z}$, then $a^3 \equiv a \pmod 3$. I know how to do proofs if there were conditional statements but not sure how to prove this with ...
1
vote
2answers
36 views

modulo group defined by an algebraic relation

I am asked if $\{n, n^{2}, n^{3}\}$ forms a group under multiplication modulo $m$ where $m = n + n^{2} + n^{3}.$ As an example we see that $\{2, 4, 8\}$ does form a group modulo $14,$ with identity ...
1
vote
3answers
65 views

Additive identity in $\mathbb{Z}_{7}$

The problem consists of two parts: 1)Prove that for some integer $m,$ $3^{m} = 1$ in the integers modulo 7, $\mathbb{Z}_{7}$, which i have done. The second part asks to use this fact to deduce that ...
6
votes
1answer
59 views

Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
0
votes
0answers
24 views

Keep a Function Positive via Mod

I have a function $F$ and I want it to remain positive--i.e., $$- F=F,\quad F=F $$ Would sticking a $\mod 2$ in front of $F$ do this? That is, because $$-1\mod 2=1\mod 2=1 $$ Then let ...
1
vote
2answers
60 views

How to solve this $ (7/2)\bmod5$?

I know its answer is $3\cdot5$ but I want to ask that is the following true- $$(a/b)\bmod(p) = (a\bmod(p))\cdot((1/b)\bmod(p)))\bmod(p)$$ (where $a$ and $b$ are any integers and $p$ is a prime ...
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
1
vote
4answers
56 views

Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
0
votes
3answers
51 views

A homework question, finding the maximum possible value of the sum of two remainders

If $a<b$ what is the maximum possible value of a mod b+ b mod a. I tried several times, the answer always came out to be 2a-2. But then it is not a choice. Am I right?
1
vote
1answer
47 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
0
votes
5answers
33 views

How many integers are there between 50 and 250 inclusive which are congruent to 1 mod 7?

Number of integers between $50$ and $250$ inclusive which are congurent to $1$ mod $7$. I understand that one could find the smallest and largest numbers in the interval $[50,250]$ that are congruent ...
1
vote
2answers
31 views

Tricks for Find Modular Inverses

I know that you can apply Euclid's Extended Algorithm, but I was wondering if there were "tricks" for guessing modular inverses. For example, if you have something like $ 13 \pmod{25}$ then you easily ...
1
vote
1answer
48 views

Solving Equations in $\mathbf{Z}/n\mathbf{Z}$ with Indices

Consider the equation $x^4 = 7,$ which we wish to solve in $\mathbf{Z}/29\mathbf{Z}.$ I was taught a technique for solving this problem, but I can't understand it. I'll try my best to describe it, ...
1
vote
0answers
24 views

generalized expression required

suppose i have a set $ {0,1,2.......x-1}$ Now I am generating an i length sequence using the numbers from above set...${a0,a1,....ai}$ where all $ai$$>=0 $ and $ai<=x-1$ Note numbers may ...
1
vote
1answer
16 views

Lagrange theorem modulo arithmetic

as far as I can see, Lagrange says: IF $p$ = prime, $p-1 = 2*q$, $q$ = prime THEN $g^q \mod p = 1 \implies \text{order}(g) = q$ $g^q \mod p \neq 1 \implies \text{order}(g) = p-1$ However if i try to ...
-2
votes
1answer
240 views

How to obtain $\operatorname{lcm}(a_1,a_2,a_3,\ldots,a_n)\%1000000007$

The problem is that you have $n$ numbers whose value can be in range $[1,100000]$. The task is to find the LCM of all these numbers. Now the answer can be very large so it should be printed MODULO ...
0
votes
2answers
33 views

calculate reverse number with 2 conditions

I can't find the reversed number of $2 \mod 13$ ($2^{-1}=?$) that is also a solution to $$5x = 2 \mod 13.$$ How can I find it? Thanks!
5
votes
3answers
60 views

Is this procedure for $5^{300} \bmod 11$ correct?

I'm new to modular exponentiation. Is this procecdure correct? $$5^{300} \bmod 11$$ $$5^{1} \bmod 11 = 5\\ 5^{2} \bmod 11 = 3\\ 5^{4} \bmod 11 = 3^2 \bmod 11 = 9\\ 5^{8} \bmod 11 = 9^2\bmod 11 = ...
3
votes
1answer
41 views

Number theory notation

I am confused with the below notations . I know that ($a \equiv b \mod {n} )\iff ( n|(a-b)$ ) but what the below notation says ? $a = b \mod {n}$ and in theorem 16 in this ,it's given as below ...
1
vote
1answer
30 views

Finding integer to satisfy modular equation.

I'm trying to find an integer x that satisfies a modular equation, and can't get my head wrapped around it... Given two integers $n$ and $m$ in the range $[0, 2^{32})$, I need to calculate an integer ...
3
votes
2answers
64 views

Are there 2D analogues for integer division and modular arithmetic?

Let's say you have a "parallelogram" of points $P = \{(0, 0), (0, 1), (1, 1), (0, 2), (1, 2)\}$. This parallelogram lies between $u = (2, 1)$ and $v = (-1, 2)$. Then for any point $n \in ...
0
votes
1answer
55 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
1
vote
1answer
67 views

Where does modulus take place

I know bedmas (brackets, exponents, division, multiplication, addition, subtraction), but there isn't a modulus in there. If I wanted to calculate a question with mod, when would I do it?
1
vote
1answer
34 views

Reverse Modulus Operator with given condition

I have an equation: $$ x^2 \mod p = z $$ $p$ and $z$ are given. $x$, $p$ and $z$ are positive integers and a maximal value of $x$ is given (say $M$). $p$ is a prime. How can i calculate (multiple ...
1
vote
2answers
39 views

Operations in finite field $F_p$

If I have a finite field $F_p$, where $p$ is prime how can I define operations like $+, -, \times, / $? Can I just make: $$add: (a + b) \mod p$$ $$sub: (a-b) \mod p$$ $$mul: (a\times b) \mod p$$ ...
2
votes
1answer
58 views

Sequence becomes constant modulo $n$

Does the sequence $$a,a^a,a^{a^a},\cdots$$ is constant modulo $n$ from a certain rank ? Where $a,n \in \mathbb{N}$ Using mathematica I am tempted to say yes but I how can I approach this ? ...
0
votes
1answer
66 views

How to find the day of the week for a given date?

Please help me with my math problem How to find the day of the week for a given date? Give some simple solution or short cut for this problem Thanks in advance
1
vote
0answers
12 views

Jacobi Form and its Fourier expansion

Let k,m be non negative integers. A Jacobi form of weight k and index m is a holomorphic function f on $\mathbb{H} x \mathbb{C}$ (where $\mathbb{H}$ denotes the upper half plane) satisfying the ...
2
votes
3answers
36 views

What are the members of the set $A=7^{n}+5^{n}(mod35)$

I have this set $A=${$\ x \ \in \mathbb{N}|\ \exists \ n \ \in \mathbb{N}:$ $x \equiv 7^{n}+5^{n}$ (mod $35$) $ $, $ 35\gt x\ge 0$} I want to know how many members has this set? thanks in advance
1
vote
2answers
36 views

How to prove that $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$)

I'd like to solve this problem but I can't $\exists \ m,n \ \in \mathbb{Z}$ & $ m\gt n\ge 0$ $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$) Any ideas? Thanks in advance.
4
votes
3answers
164 views

Square roots modulo powers of 2

Experimentally, it seems like every $a\equiv1\left(\bmod\,8\right)$ has 4 square roots mod $2^n$ for all $n \ge 3$ (ie solutions to $x^2\equiv a\left(\bmod\,2^n\right)$) Is this true? If so, how can ...
3
votes
2answers
152 views

Number theory problem.Primes modules.

If $$a^p\equiv b^p \pmod p$$ where $p$ is prime prove that $$a^p\equiv b^p \pmod{p^2}$$ that problem was at my exam today on number theory and i just didnt have a clear mind to solve it.Although i ...
2
votes
2answers
40 views

Correct reasoning when proving the multiplication property in modular arithmetic?

I am trying to understand why this rule works: \begin{align*} a \equiv b \pmod c \quad k \equiv j \pmod c \qquad &\implies \qquad ka\equiv jb \pmod c \end{align*} I saw that the proof is ...
1
vote
1answer
14 views

Definition for a distance function over a residue class ring

I'm searching for a reasonable definition of a distance function $$d:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\to\mathbb{N}_0$$ which satisfies $d(\overline{n-1},0)=1$ ...