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
19 views

Testing for Linear Independence/rank mod m

I am working on cracking a hill cypher using modular linear algebra. Every example I have found online makes a big assumption that is not necessarily the case, and as I see it leaves a lot to be ...
0
votes
0answers
28 views

Proof for a relation

Define a relationship $R$ on $\mathbb{Z}$ by declaring that $xRy$ if and only if $x^2 \equiv y^2 (mod 4)$. Prove that $R$ is reflexive, symmetric and transitive. I'm unsure of where to start with ...
1
vote
4answers
140 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
1
vote
3answers
36 views

Modulo operation. How to prove it?

I noticed relation between modulo operation and number which is power of two Example I have to calculate $ 3431242341 \mod 2^5 $, which is $ 5 $ but it is equivalent to $ ( 3431242341 \mod 2^9 ) ...
3
votes
1answer
46 views
+50

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
1
vote
0answers
40 views

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$?

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$? I'm 99% sure this is an application of the Chinese remainder theorem, although my workings do not quite show how it can be ...
0
votes
0answers
17 views

Simplifying the expression involving mods

I'm trying to simplify the following expression (I hope to be able to write it in a nicer form) but I cannot: For $m \in \mathbb{N}$ and $n \in \mathbb{N}$, $l(m)$ is defined as \begin{equation*} l(m) ...
1
vote
5answers
83 views

finding mod of an expression with variables

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 (\bmod 6)$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 (\mod 2)$ so ...
0
votes
1answer
27 views

Converting infinite base-k expansions into base-j expansions

I understood the method of transforming a finite sized base-k numbers to another base (j) through the use of successive divisions For example $$12_{10} = 12/2 + 0*2^0 = 6/2 + 0*2^1 + 0*2^0 = 3/2 + ...
0
votes
2answers
42 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
87 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
17 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
40 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
28 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
36 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
3answers
57 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
108 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 ...
41
votes
4answers
3k 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
2answers
109 views

Congruence modulo primes or in a polynomial ring over ${\rm GF}(2)$

Let $p, q$ be primes. Then the linear congruence $$ap \equiv r\pmod q$$ can be solved for $a\in\mathbb Z$ and will have a unique solution for each value of $r$ such that $0\leqslant a<q$. Am I ...
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
43 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
34 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
67 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
186 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
57 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
49 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
35 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
32 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
17 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
241 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
67 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
68 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$$ ...