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
0answers
22 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
57 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
158 views

Why elements of the set can be Goldbach pairs for a given even number? [on hold]

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
5answers
54 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
49 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
37 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
32 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
30 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
47 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
239 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
57 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
64 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
35 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
34 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
162 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$ ...
3
votes
3answers
100 views

How to find the missing number?

A teacher intended to give a typist a list of nine integers that form a group under multiplication modulo 91. But one of the nine integers was inadvertently left out, so that the list appeared as ...
7
votes
1answer
74 views

$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $

Show that $$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $$ Indeed, First let's show $7\mid x \text{ and } 7\mid y \Longrightarrow 7\mid x^2+y^2 $ we've $7\mid x ...
2
votes
1answer
45 views

How Many of a Given Weekday Fall in a Month

A month can have either $31, 30$, or $28$ days excluding leap years. Suppose we want to know "how many Fridays are in a given month". By considering the maximal case where the first Friday falls on ...
0
votes
2answers
46 views

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$? I have made several observations about the problem but I cant see how they lead me to an answer. Observation one: ...
0
votes
1answer
40 views

Polynomial Diophantine Equations

So in general how does one decide if: $$ a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers $x,y$ given real numbers $a_0, a_1. .. a_{n_1}, b_1 , ...
0
votes
1answer
31 views

Fundamental theorem of algebra in modular arithmetic

suppose you have a polynomial $P(x) = a_0+a_1x+...+a_kx^k$. How can you prove that at most $k$ numbers satisfy $P(x) \equiv 1 \mod n$ ? To me this looks like the fundamental theorem of algebra, ...
0
votes
1answer
16 views

When will function output have a specific decimal component

Given a function f(x), is there any way to predict when the function will give a specific decimal part without brute-force iteration over possible x-values? Ex. f(x)=100/a^2 with arbitrary a, when ...
1
vote
1answer
31 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
1
vote
2answers
78 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
1
vote
1answer
17 views

Bound on the degree of a determinant of a polynomial matrix

I want to implement a modular algorithm for computing the determinant of a square Matrix with multivariate polynomials in $\mathbb{Z}$ as components (symbolically). My idea is first to reduce the ...
3
votes
0answers
38 views

Strange things on WolframAlpha: derivation, modulo and doubling result

I asked WA what is the derivative of $\frac1{\cos((x \bmod \pi/2)-\pi/4))}$ equal to for $x=0$. A very strange result came out. The exact result is $-\sqrt2 \mathsf{Mod}^{(1,0)}(0,\frac\pi2)$, ...
0
votes
1answer
7 views

contextual system of congruences

A large wholesale company for books uses three different types of shelf in their ware- houses. Their capacity is gauged in terms of a certain specimen book of average size, known under the nickname ...
3
votes
2answers
18 views

How do I eliminate mod from an expression?

If I have an expression such as $$ x = ((a \bmod b) - s) \bmod t, \quad 0 < a < b $$ And I want to step to $$ x = (a - s) \bmod t $$ Is acceptable to jump straight from the first expression to ...
1
vote
3answers
73 views

A question about modular arithmetic

$2^{35}\equiv x\bmod 561$ I have seen this in my book but there is no solution in it, how can we find x?
0
votes
3answers
21 views

Find all solutions for modulo equation

Given $(133x \equiv 107) \pmod{91} , x \in N $ My first attempt was to do: $133x - 91z \equiv 16 \pmod{91}$ $133x - (91z + 16) \equiv 0 \pmod{91}$ $133x - 16 \equiv 0 \pmod{91}$ From there on I do ...
2
votes
1answer
13 views

Polynomial factorisation on integers modulo n

Is there a known (efficient) algorithm to compute the list of factors of a polynomial modulo $n$ (for any integer $n$)? For example in $\mathbb Z_8$, $X^2+2X$ has a list of 4 factors (multiplicity 1 ...
0
votes
1answer
26 views

Proof that the repeating block of digits in 1/x is at max x-1?

The question is self-explanatory, I suppose. Example, the maximum number of digits in the repeating block of 1/17 is 16. Thanks in advance.
0
votes
1answer
44 views

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd.

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd. This is a problem from ISI 2014 written test in a little ...
2
votes
3answers
98 views

How do you prove that $ n^5$ is congruent to $ n$ mod 10? [duplicate]

How do you prove that $n^5 \equiv n\pmod {10}$ Hint given was- Fermat little theorem. Kindly help me out. This is applicable to all positive integers $n$
2
votes
1answer
43 views

The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3 $$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...