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

32
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 ...
2
votes
3answers
44 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
32 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.
1
vote
1answer
287 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
0
votes
0answers
36 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 ...
0
votes
3answers
31 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 ...
0
votes
4answers
51 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.
7
votes
1answer
78 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 ...
1
vote
2answers
40 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
49 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
41 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 ...
0
votes
3answers
95 views

If the sum $\sum_{x=1}^{100}x!$ is divided by $36$, how to find the remainder?

If the sum $$\sum_{x=1}^{100}x!$$ is divided by $36$, the remainder is $9$. But how is it? THIS said me that problem is $9\mod 36$, but how did we get it?
0
votes
1answer
182 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
2answers
35 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
23 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 ...
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?
1
vote
2answers
79 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 ...
0
votes
3answers
50 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 ...
3
votes
0answers
112 views

Fast way to find the smallest root $\mod M$ of a polynomial

Suppose you're given a polynomial of degree $d$ with integer coefficients: $$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$ Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite ...
1
vote
2answers
56 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
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, ...
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
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
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 ...
0
votes
2answers
312 views

Modular Arithmetic Calendars

If a calendar has 427 days in the year and 8 days a week and the first day of their current year, which is 1027 falls on the second day of their week. What day of the week will the first day of the ...
1
vote
2answers
498 views

Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
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 ...
25
votes
5answers
4k views

Prove that every year has at least one Friday the 13th

Everyone knows Friday the 13th is regarded as a day of bad luck. Why does every year have at least one of this bad day?
0
votes
3answers
150 views

Book on modular arithmetic

I am searching for some good book which section is devoted to modular arithmetic. I am self learner so I strongly prefer that book has exercises best with answers or solutions. I have CS background ...
-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 ...
0
votes
2answers
210 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
4
votes
3answers
593 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
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 ...
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 ...
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?
2
votes
0answers
39 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
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 ...
0
votes
1answer
65 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
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
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 ...