Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [modular-arithmetic]

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 $a-b$.

0
votes
1answer
21 views

Congruence of integers and primitive roots

Lemma: In $\mathbb{Z}$, if $l\ge 1$, $p$ any prime, and $x\equiv y\pmod{p^l}$ then $x^p\equiv y^p\pmod{p^{l+1}}$. The proof is by Binomial theorem. Assume the Lemma. Suppose $x^{p^l}\equiv 1\pmod{...
2
votes
2answers
53 views

Remainder of $(1\cdot2\cdots102)^3$ modulo $105?$

I am having trouble in finding the remainder of $(1\cdot2\cdots102)^3\mod 105$ It is not possible to apply Wilson's Theorem here because 105 is composite. Can anybody help me?
0
votes
3answers
23 views

Multiplicative order when gcd=1

If $a^{n}\equiv 1 \pmod m$, then $aa^{n-1}\equiv 1 \pmod m$, so $a^{n-1}$ is the multiplicative inverse of $a$ modulo $m$ and $\gcd(a,m)=1$. What I don't understand is why $\gcd(a,m)=1$ and $a^{n}\...
1
vote
1answer
35 views

Count number of roots of polynomial modulo prime power

I found this problem in a number theory course, I am assuming (but not sure) it is supposed to be an application of Hensel's lemma. For every $n \in \mathbb{N}_0$, determine the number of solutions ...
1
vote
0answers
46 views

Math game problem, not able to understand why the solution works?

Players A and B Rules of the game: The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches. The players alternate turns; A ...
0
votes
0answers
44 views

Plotting points of the form $-p \mod(n)$

Imagine taking an interval $[-n,n]$ of the $x$-axis, cutting it in half at $x=0,$ and gluing the sides over top of each other. This process is equivalent to thinking about points of the form: $-x \...
2
votes
1answer
14 views

A difference in a formula of theorem 4.2(e) on congruence relations.

The statement of the theorem said : If $a \equiv b \pmod n$ then $ac \equiv bc \pmod n$. But I have seen it in other place as: $a \equiv b \pmod n$ then $ac \equiv bc \pmod {nc}$. Are they ...
0
votes
0answers
30 views

Finding small solutions to modular congruences

I was wondering what computational/algorithmic techniques can be used to solve a modular congruence when we are looking for a pair of small values. The specific problem is like this (the numbers are ...
1
vote
2answers
23 views

Divisibility of number $s\perp 10$

I found a property that for $s\perp 10$ we can say that there exists such $k$ that $$ 10^k \equiv 1 \pmod s $$ but I cannot prove it. Can you help me in this task. My approach: When $s\perp 10$ then ...
1
vote
1answer
31 views

time the pseudo random generator gonna start repeating itself

as you know the general formula for pseudo random generator is this U(n)=a*U(n−1)+b [mod z] where we have control of U(n-1)...
3
votes
2answers
80 views

If $a^{m}+1|a^{n}+1$ then prove that m|n.

Actually I know a similar proof which is, $a^{m}-1|a^{n}-1 \iff a|n$ But I can't prove this. I also need some examples of the question. Can't seem to find any correlation between the two proofs. I ...
0
votes
0answers
43 views

Computing modular inverses $65537^{-1\!}\bmod (10^n\!-1)$ for large $n$

I have the following formula: $$d \cdot 65537 \equiv 1 \pmod{9999...}$$ I have to find $d$, even in case the modulo is 30 digits long. This means I am not supposed to brute force it, but I haven't ...
0
votes
0answers
19 views

How to algebraically mirror a finite subset of integers? [on hold]

Let's take the set $S=\{0,1,...8,,9\}$ as an example. By mirroring I mean creating a function $f$ such that $f(x) = x$ is $x \in \{0, 4\}$ and $f(x) = 4 -(x \equiv 5)$ otherwise. The above however ...
1
vote
1answer
57 views

Knowing that $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$

Knowing that $a,b$ are prime integers and $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$ I used $a^7+b^7=(a+b)(a^6-a^5b+a^4b^2-a^3b^3+a^2b^4-ab^5+b^6)$ and tried to show that ...
1
vote
0answers
29 views

Finding the modular of a Square Root of a product of many numbers

I am working on Quadratic Sieve and at some stage I need to find $$ \sqrt{\prod_{k=1}^n y_k} \pmod{N} $$ Now the Product (inside square root) getting bigger and bigger (up to few hundred numbers) and ...
1
vote
1answer
27 views

Assumptions in Artin's primitive root conjecture

I'm having a little trouble, understanding the necessity of the assumptions in Artin's Conjecture. Artin's primitive root conjecture states, that: for any $$a\in \mathbb{Z}\setminus \{-1\}$$ and $$...
1
vote
3answers
59 views

Primes number $n,n+2,n+6,n+8,n+12,n+14$

Find all natural number $n$ such that all the following numbers are primes : $$n,\;\; n+2,\;\;n+6,\;\;n+8,\;\;n+12,\;\;n+14$$ are all prime numbers
0
votes
2answers
29 views

Modulo multiplicative inverse

In ax $\equiv$ 1 (mod m) , when gcd(a, m) = 1, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique. This is written in wikipedia. I am confused ...
2
votes
4answers
101 views

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333…3.(100 3's)

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333...3.(100 3's). My approach: we see that 111 is divisible by 3. Hence 100 3's would divide 300 1's. Is my ...
0
votes
1answer
22 views

-1 as a Quadratic Residue mod $p$ $\Rightarrow$ $p \equiv_4 1$ [duplicate]

Suppose $p$ is odd prime. If $x^2 \equiv_p -1$, show $(x^2)^{\frac{p-1}{2}} \equiv_p 1$, and conclude that $p \equiv_4 1$ ( I cannot get to this part for some stupid reason) Here is what I have, ...
1
vote
2answers
40 views

If $a \equiv 9 \pmod {12}$, find all possible values for $\gcd(a^2+21a+72,252)$

We know that $$a^2+21a+72 \equiv 9^2 + 21 \cdot 9 + 0 \equiv 6 \pmod {12}$$ So we know that that expression, let's say $\alpha$, is such that $12 \mid \alpha - 6$. But then $12 \mid 2(\alpha - 6)=2a+...
0
votes
1answer
66 views

Is there a specific theorem or name for this particular fact about primes? (Mod 6)

Is there a particular theorem or name defining the property/behavior of primes such that all primes (greater than 3) are congruent to 1 or 5 (mod 6)? I could have sworn I saw one years ago, but I ...
2
votes
3answers
78 views

Prove that $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 9 = 7$

Prove that $\underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{2016 \mbox{ times}} \mod 9 = 7$ I think that it can be done by induction: Base: $2^{2^{2^{2}}} \equiv 2^{16} \equiv 2^8 \cdot 2^8 \equiv 2^...
1
vote
2answers
46 views

$a \equiv b \mod k \implies a \equiv ? \mod k^2$?

Is there any modular law such that: $a \equiv b \mod k \implies a \equiv ? \mod k^2$ I know that $$ a \equiv b \mod k \implies a^n \equiv b^n \mod k $$ but sometimes I need to power only $k$ and ...
2
votes
1answer
65 views

Congruence equation with power solving method

How can the equation like $$ x^{118}\equiv 113\;\; (mod\; 1001) $$ if I know the Fermat's little theorem, Chinese remainder theorem, Euler's theorem and basic operations on congruence? My approach: ...
1
vote
1answer
39 views

Modulo congruences and remainder

Let $x \in \mathbb{Z}$ Show that if $N\mid M$ then $(x\pmod M)\pmod N = x \pmod N$ My proof: Assume $x \in \mathbb{Z}$ is arbitrary. Then define $x\pmod M =r \iff x \equiv r\pmod M$ where $0\leq r &...
0
votes
1answer
38 views

Modular aritmetic and fields

I'm studying the concept of field applied to modular aritmetic. Is it correct to say that, if the dimension is a prime number $p$ then field properties are satisfied for the integers $\bmod p$ ? And ...
1
vote
1answer
36 views

Why is it that only exponents that are divisors of φ(N) capable of generating the identity element as a power when N is prime?

Let $p=x$ where $a^x \equiv 1\pmod N$. When $N$ is prime I can check whether $p=N-1$ and if it is, there are a full set of remainders. However, if $p<N-1$, I need to keep checking. For example, if $...
1
vote
1answer
37 views

Use congruence to show that the output of a natural number function is always divisible by 6 [duplicate]

I have been asked to show that for any natural number $n$, $(7n+30)(13n+7)(n+2)$ is divisible by 6. I can show that this function is congruent to $n(n+1)(n+2)$. I noticed that this function is the ...
1
vote
1answer
46 views

Given 2 functions $f(x)$ and $g(x)$ find a value where $g(x)$ divides $f(x)$ meaning $f(x) = 0 \mod g(x)$

Problem: Given 2 functions $f(x) = 2^{p-1} + x*p$ and $g(x) = 2 * x * p + 1$ find the values where $f(x) = 0 \mod{g(x)}$, where $p$ is a prime number and $x$ is a non negative integer in the range $1,...
1
vote
1answer
30 views

Congruences and second-order recurrence relations

I'm having trouble tackling this ghastly exercise. Let $(a_n)_{n\in\mathbb{N}}:a_1=3,a_2=-1,a_{n+1}=a_{n+1}+4^{2n}a_n+15^n n^{15}$. Prove that $a_n \equiv 3^n \pmod 5$. I know that every term in ...
0
votes
2answers
39 views

Finding the remainder of the division of $\sum_{i=0}^{102} i^6+i$ by 4 and by 5

I reasoned it this way: divisibility by 4 has 4 congruence classes. Only two of these are such that $a^6 + a \equiv 2 \pmod 4$; the others have no remainder. In $\sum_{i=0}^{102} i^6+i$ there are 52 ...
-2
votes
1answer
32 views

What's the remainder when divided by 4 [closed]

Determine the remainder of $n$ when divided by 4 $$n=\sum_{k=1}^{50} k^k$$
2
votes
4answers
83 views

Prove that for all $n \in \mathbb{N}$, either 3 or 13 divides $3^n + 13n^2 + 38$

Let $a\in \{3,13\}.$ I'm having trouble with this proof. I know that $$3^{n+1} + 13(n+1)^2 + 38 = (3^n + 13n^2 + 38) + (2\cdot 3^n + 26n + 13)$$ But I can't prove that $a \mid 2\cdot3^n + 26n + 13$. ...
2
votes
1answer
42 views

The Chinese Remainder when the residues are 1

$\newcommand{\mod}{\operatorname{mod}}$I'm trying to understand how the Euler Theorem is generalized to any number. So we have $n$ as a multiplication of powers of prime number. I can prove that an m ...
0
votes
1answer
28 views

How is it that (p-1)! is not congruent with 0 mod p if p is prime?

Why is this statement true? If $p$ is prime then $(p-1)! \not\equiv 0\space mod\space p$. I would like to know why this is true.
2
votes
1answer
25 views

Prove a property of Legendre symbol

In case someone does not know the definition, I first write down the definition. Def Let $a$ be s.t. $(a,m)=1$. Then we say $a$ is a quadratic residue modulo m if the congruence $x^2\equiv a$ (mod $m$...
2
votes
0answers
34 views

Expected number of distinct sums of two sets modulo an integer

Let $m$ be a fixed integer and $r,s\ll m$ given integers. We pick uniformly at random two sets $A$ and $B$ of classes modulo $m$ the first with $r$ elements and the second with $s$ elements. I would ...
1
vote
2answers
56 views

Can the number $2^n + n^2$ be divisible by $5$ for some natural number $n$?

Can the number $2^n + n^2$ be divisible by $5$ for some natural number $n$? I found some solutions, i.e., $n=6, n=8, n=12, n=14$ but not 18 or 20 by trial and error and somewhere I realized that the ...
3
votes
1answer
105 views

Large modular n'th roots, e.g. solve $\,x^{118}\equiv 113\pmod{\!1001}$

Solve $$\exists_k \mbox{ } 1001\cdot k+113 = x^{118} $$ How to deal when I have something like in that exercise when my big number is $ 13\cdot 11 \cdot 7$? My current way: It is equivalent to: $$ ...
1
vote
2answers
52 views

Solve the congruence by using the method of completing the square

Actually, I found a open problem which is the same as my problem, see Solve quadratic congruence equation by completing square. But I can not understand the answers...they are too brief... My typical ...
2
votes
1answer
73 views

Divisibility of cubes by 7

Show that if if $x^3+y^3=z^3$ for some $x,y,z$ $ \in \mathbb{Z}$ then one of $x,y,z$ is divisible by $7$. I'm stuck on this problem. I know that for any integer $n\in \mathbb{Z}$, $[n^3 \pmod{7}]$ $\...
4
votes
2answers
92 views

Solve $99x^2 \equiv 1 \mod 125$

Solve $$x^{98} \equiv 99 \mod 125$$ Is there any easy way to solve equations like that? My observation is that from Euler's theorem we know that $$ x^{100} \equiv 1 \mod 125 $$ so $$x^{98} \equiv 99 \...
1
vote
4answers
33 views

Why $99x^2 \equiv 1 \mod 5 \implies (-1)x^2 \equiv 1 \mod 5$

Lastly I have read a example of some exercise. There was this statement: $$99x^2 \equiv 1 \pmod 5\quad \implies\quad (-1)x^2 \equiv 1 \pmod 5$$ Can somebody explain that simple fact to me?
1
vote
2answers
37 views

How to solve this quadratic congruent equation by inspection

I found a systematic way (c.f. How to solve this quadratic congruence equation) to solve all congruent equations of the form of $ax^2+bx+c=0\pmod{p}$, or to determine that they have no solution. But ...
0
votes
2answers
76 views

$1234x+567y=89$

I need to solve this with congruence. What I already done is : $$1234x+567y=89$$ $$1234x\equiv 89\bmod 567$$ $$1234\cdot17x\equiv 89\cdot17\bmod 567$$ $$20978x\equiv 1513\bmod 567$$ $$x\equiv -1513\...
0
votes
1answer
31 views

How do I solve the second part of this question? [closed]

A. Find the modular reciprocal of 1000 in ℤ 1253. B. Find an integer x ∈ ℤ 1253 that solves 1000 ⊗ x = 13 in ℤ 1253. I solved the first part by using the extended euclidean algorithm, and I ...
2
votes
3answers
88 views

How many integers $m$ such that $9^m - m$ is divisible by $65$

How many integers $m$ such that $9^m - m$ is divisible by $65$ where $1\le m \le 1000$ $\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}$ My approach Generally we want to solve: $$ 9^m \equiv m \Mod{65} ...
2
votes
4answers
95 views

Fastest way to solve congruency equation

I've developed an equation that solves a problem I'm working on, but the only way I know how to solve it is by incrementally trying values of $n$ from $1 \to \infty$ until I arrive at the solution. ...
1
vote
1answer
33 views

matrix elements correspondence

I have a $8\times 8$ matrix $A$, I want to break it into $4$ slices each of size $4\times 4$, this way I have a cube of $B$ of size $4\times 4\times 4$. The slices are cut out taking each $4\times 4$ ...