Stack Exchange Network

Stack Exchange network consists of 174 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
13 views

Find two distinct group homomorphisms between $(U_{11}, *)$ and $(\mathbb{Z}_{10}, +)$

Find two distinct group homomorphisms between $(U_{11}, *)$ and $(\mathbb{Z}_{10}, +)$, where $U_{11} =$ set of units in $\mathbb{Z}_{11}$. My observations: We want to create a function $f: (U_{11}, *...
-2
votes
1answer
76 views

Find a $x$ such that $2^{2015}x\equiv 1 \pmod{13}$ [on hold]

Since 13 is prime number using little Fermat's theorem $2^{12}\equiv 1 \pmod {13}$ then $2^{2015}\equiv 2^{12\cdot167+11}\equiv 2^{11} \pmod{13}$ then $2^{2015} x \equiv 2^{11} x \equiv 1 \pmod{13}$ ...
0
votes
0answers
28 views

Prove that $n$ is not divider of number $2^n-1$, if $n>1$ [duplicate]

Prove that $n$ is not divider of number $2^n-1$, if $n>1$ If we think opposite, then $n$ is divider of number $2^{n}-1$, since $2^{n}-1$ is odd number then $n\not=2k$, where $k\in \mathbb Z$, now ...
0
votes
1answer
16 views

Proof involving congruence of integers with a biconditional

For any set S = {a, a+1, ..., a+5} where 6|a, 24|($x^2$ - $y^2$) for distinct odd integer x and y in set S if and only if one of x and y is congruent to 1 modulo 6 and the other is congruent to 5 ...
0
votes
0answers
26 views

Show that there exists infinitely many primes which satisfy a given congurence.

Let $m$ be a fixed positive integer that is the product of distinct prime factors of the form $(3k+2)$, such as $5 \times 11$. Prove that there exist infinitely many primes $p$ such that $3^{3p-2}\...
0
votes
0answers
13 views

Additive bijection between module sets.

This is already been solved, but lacks of what is inteded by additive bijection. Could someone tell me what is the meaning of the map? (like how would I read that, in the sense of how is the ...
1
vote
1answer
60 views

A mod 2 binomial identity

I would like to show the following identity: for all $n, q \geq 0$, $$\sum_k \binom{2k}{4k-2n} \binom{n+3q}{2k+2q+1} \equiv \binom{n+3q}{2q-1} \pmod{2}.$$ This has been computer-tested for all $n, ...
0
votes
3answers
41 views

Modulo operation for integers and reals?

I read that the modulo operation finds remainder after division. My misconseption here is about the remainder. Is the remainder the last digit of the result? I thought it was the first. Example: $5/7 ...
0
votes
1answer
24 views

Find a Matrix A on the ring of integers modulo 3 so that KerA=ImB.

B={{1,1,1},{0,1,2},{2,1,0},{0,2,2}} I understand that each vector from then span of column vectors of B is a solution for Ax=o and that matrix A should have four columns. However I don't know how ...
0
votes
0answers
18 views

Function mapping a number $\mod 8$ and power of 2 representation

Define $n\in\mathbb{N}$ Let me also represent the number $n$ in exponential form as the sums of power of twos. How can we then remove the powers where the exponent is greater than $2$? So what we ...
1
vote
2answers
57 views

Proof that Sylvester numbers, when reduced modulo 864 , form an arithmetic progression 7,43,79,115,151,187,223,…

The following observation has been made: Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$ This has been ...
0
votes
0answers
66 views

Fermat-Catalan eighth powers

There are two Fermat-Catalan solutions that have as an eighth power in their addend the numbers, $33^8$ and $44^8$. In Darmon and Granville's paper, they show that the generalized Fermat Equation has ...
1
vote
3answers
25 views

Show that: $a·c \equiv b·c\ (\text{mod }m)$ with $a, b, c$ and $m$ integers with $m \ge 2$ does not imply $a \equiv b\ (\text{mod }m)$

Show that $a·c\equiv b·c\ (\text{mod }m)$ with $a, b, c$ and $m$ integers with $m \ge 2$ does not imply $a \equiv b\ (\text{mod }m)$ I've seen many similar examples, but can't seem to find a step by ...
4
votes
0answers
30 views

Visualizing rational numbers as multiplication graphs

It's an interesting fact, that there's a straight forward way to visualize rational numbers. To each rational number – given as two integers $n<m$ – there corresponds a multiplication ...
2
votes
4answers
65 views

Prove that $2005|\underbrace{55 \ldots5}_{800\text{ digits}}$

Prove that $2005|\underbrace{55 \ldots 5}_{800\text{ digits}}$ I know that $2005=5\cdot 401$ since $55 \ldots 5$ is divisibility with $5$ i only need to prove that $55 \ldots 5$ is divisibility with ...
1
vote
3answers
63 views

Integer solutions of a variable coefficient polynomial

I have many equations to solve similar to this one: $$2 a b^3 - a b^2 + a b - 2 a - b^4 + b^3 - 2 b^2 + 2 b = 0$$ Here, b is a base and a is a non-zero digit in a b-adic number, so $1 \leq a \leq b-...
1
vote
2answers
29 views

Congruence with algebraic exponents

I have done a number of congruence questions but then I encountered this question: $7^{x+2} ≡ 5(mod 29)$ How do you go around solving this? I thought of splitting the powers to $7^x$ and $7^2$ but ...
1
vote
1answer
16 views

finding m for which modular arithmetic statement is true

Suppose for all $n\in\mathbb Z$, we have $(x + 4n)^2\equiv x^2\bmod m$. Find all $m\in\mathbb N$ for which this is a true statement. I have no idea how to go about finding m. I tried to use the fact ...
0
votes
3answers
32 views

How to show $2l+1\equiv (2l+1)^{4n+1}\pmod{5}, \forall l$ in the integers?

How would I go about showing $2l+1\equiv (2l+1)^{4n+1}\pmod{5}, \forall l$ in the integers? I tried this, but got stuck. \begin{align*} 2l+1&\equiv x\pmod{5}\\ (...
1
vote
1answer
48 views

If $m$ and $n$ are relatively prime positive integers, prove that $m^{\phi(n)}+n^{\phi(m)}\equiv1\pmod{mn}$ [duplicate]

I have found this question answered before but I am stuck going from $$m^{\phi(n)}+n^{\phi(m)}\equiv1 \pmod{n}\\ n^{\phi(m)}+m^{\phi(n)}\equiv1 \pmod{m}$$ to $$m^{\phi(n)}+n^{\phi(m)}\equiv1 \pmod{mn}...
0
votes
0answers
17 views

special interior angles of regular $n$-gon

Let $K$ be a regular $n$-gon in the plane. Assume the following: $$n\in\Bbb N,\quad n\geq3\\I=\{0,1,...,n-1\}\\ \forall i\in I, \quad M(i):=\operatorname{mod}(i,n)$$ And we define $P_i$ as the $i$-th ...
0
votes
0answers
16 views

Period finding: Why x^r (mod N) is a periodic function?

If I take an example, I can observe that it is the case, but I am not able to understand why an exponentially rising function x^r would hit say x^r (mod N) periodically. r is a variable here, and x ...
1
vote
0answers
22 views

Structure of $i^n \ mod \ p, 1 \leq i <p$ where $p$ is a prime congruent to $3$ mod $4$

I'd like to ask how to describe the structure of $i^n \ mod \ p, 1 \leq i <p$. Can all the values be constructed using some direct products of some generators? What is the size of the set of values?...
1
vote
1answer
22 views

How to calculate all possible values for $m$, where $m=i^k \mod p$, $k,p$ are fixed?

For example, all possible values for $i^{10} \mod 71$ is $1, 20, 30, 32, 37, 45, 48$. Is it possible to directly calculate these values without trying all possible $i$ from 1 to 71?
2
votes
0answers
21 views

Find $\prod_{i=1}^{p-1} (i^{2st}+1) \pmod p$ where $s<t$ are primes congruent to $1$ modulo $4$

I'd like to ask how to calculate $$\prod_{i=1}^{p-1} (i^{2st}+1) \pmod p$$ where $s<t$ are primes congruent to $1$ modulo $4$, for any odd prime $p$. Here're some partial results. For any $1\...
1
vote
1answer
23 views

$\prod_{i=1}^{p-1} (i^2+1) \equiv 4 \pmod p$ if $p$ is a prime $\equiv3\pmod 4$

I find that $\prod_{i=1}^{p-1} (i^2+1) \equiv 4 \pmod p$ if $p$ is a prime congruent to $3$ mod $4$, which is verified for small primes. I'd like to ask how to prove it.
0
votes
0answers
15 views

If d = gcd(a, m) and d|c, then show that the congruence ax ≡ c (mod m) is equivalent to a x≡c (modm).

If $d = \gcd(a, m)$ and $d|c$, then show that the congruence $ax \equiv c$ (mod $m$) is equivalent to $$\frac{a}{d} x \equiv \frac{c}{d} \mod \frac{m}{d} .$$
0
votes
0answers
47 views

Which numbers will iterate to others under the Collatz iteration?

I have a question about the Collatz conjecture and how some numbers merge trajectories. Take the standard map: $$C(n) = \begin{cases} n/2, & \text{if $n \equiv 0$ mod $2$} \\ 3n+1, & \text{...
0
votes
0answers
30 views

Modular incongruences and Chinese Remainder Theorem

Is there a way to adapt the Chinese remainder theorem to solve a series of modular incongruences, e.g. $n \not\equiv 0\ (\textrm{mod } 5)$ $n \not\equiv 0\ (\textrm{mod } 6)$ $n \not\equiv 0\ (\...
3
votes
0answers
37 views

Some questions concerning the generators of cyclic groups

Let $g(p)$ be the least positive primitive root of the prime $p$, the primitive roots being the generators of the cyclic group $\mathbb{Z}_{p-1}$. These are the values for the first prime numbers: $$...
0
votes
1answer
26 views

In modular arithmetic, why is (x mod n)^y mod n == x^y mod n?

Why is (x mod n)^y mod n == x^y mod n? It seems to me like there is a property in modular arithmetic that explains why, does anyone have a simple way of explaining ...
0
votes
3answers
23 views

How to solve this equation for d [closed]

Solve 17d mod 24 = 1. Would it be d = 17 inverse mod 24 and then solved using EEA?
0
votes
2answers
41 views

Prove that it does not exist two number such that $m^2+n^2=6 \underbrace {0 \cdots 0}$

Prove that it does not exist a two number $m,n\in \mathbb N$ such that $m^2+n^2=6 \underbrace {0 \cdots 0}$, in solution he choose to divide by 9, but i do not know why that number, I know that ...
11
votes
2answers
812 views

Making modular arithmetic interesting for school kids

This is a pattern even school kids could discover (when gently pointed to). I never did conciously, and cannot remember to have been pointed to explicitly, neither at school nor later: $$\color{red}{\...
1
vote
2answers
57 views

Determine the remainder

Determine the remainder when $2^{2018}$ is divided by $55$
0
votes
1answer
32 views

Squares from 1 to 10000 that have a remainder of 2 when divided by 7

Find the number of integers $1\leq x\leq100$ such that $x^2$ has a remainder of $2$ when divided by $7$.
0
votes
0answers
12 views

Constant-dependent rewrite rules in Mixed-Boolean-Arithmetic expression

On page 106 of in this document, There's an example formula of a "Constant-dependent rewrite rules" [5.4.4]. See below: $$ x\oplus42 = ((x \lor 191) \land (x \oplus 106)) + (x \land 64) $$ ...
2
votes
2answers
47 views

Solving $m^3 \equiv n^6 \pmod{19}$

I'm studying for a first year Discrete Mathematics course, I found this question on a previous paper and am lost on how to solve: Let $n$ be a fixed arbitrary integer, prove that there are ...
0
votes
1answer
68 views

How to solve $a x \equiv 1 \pmod{b y}$? [on hold]

Is there a mathematical formula (not include iteration nor recursive) which can solve $a x \equiv 1 \pmod{b y}$ ? Note: $a$ and $b$ are certain integers, while $x$ and $y$ are arbitrary integer which ...
1
vote
1answer
21 views

Is there a way of calculating the exponent x after a modulo?

Is it possible to calculate x, knowing all other parameters? $y = b^x \pmod c$ My intention would be to do this with the logarithm but this brings up a new unkown parameter n: $y+nc= b^x$ $x = \...
0
votes
0answers
24 views

Defining a set of all possible non-congruent integer values

"Say Peter has discovered that $82$ and $723$ are coprime. He now believes that the equation below has a solution for all possible integer values of $q$. $$82p ≡ q\pmod {723},$$ where $p∈$ $\Bbb Z$...
0
votes
1answer
65 views

Prime solutions to a congruence modulo a semi-prime

Let $p$ and $q$ be primes. Besides $\{3,13\}$ and $\{13,61\}$, find other solutions $\{p,q\}$ to the congruence $$ 1+ p+q+p^2+q^2 \equiv 0 \pmod {pq}$$ or show that there are none.
2
votes
2answers
24 views

Get all values for exponent in congruential equation

I am stuck on an exercise on modular arithmetic. I found a similar question here, but I don't think it answers my question completely. My problem is: Solve $$ 2^x \equiv 11 \pmod {21} $$ ...
2
votes
1answer
24 views

Elementary Number Theory - Determining if there exist roots for a polynomial congruence with a prime modulus

If we consider something like the polynomial $f(x) = x^3-1$, and we want to know if there exists any solutions at all for $x^3 - 1 \equiv 0 \ (mod \ p)$, where $p$ is prime, is there a way to answer ...
1
vote
1answer
50 views

How to find all primitive roots modulo 121?

This question is different from this question as I want to find all primitive roots, and not just some. Is my following approach correct? We have $121=11^2$, with $11$ an odd prime, and $2 \ge 1$, ...
1
vote
1answer
38 views

$g^{0p^nk}+g^{p^nk}+g^{2p^nk}+…+g^{(p-2)p^nk} \equiv 0$ (mod $p^n)$ if $p-1$ doesn't divide $k$

Let $p$ be prime and $n\geq 1$. Let $g$ be the integer equivalent of some generator for $(\mathbb{Z}/p\mathbb{Z})^ \times$. Let $k\in \{0,1,2,...\} \subseteq \mathbb{Z}$ such that $p-1$ does NOT ...
0
votes
2answers
38 views

How can I prove that $n^4=1\pmod 5$ for all $(n,5)=1$.

How can I prove that $n^4=1\pmod 5$ for all $(n,5)=1$. This what I have been thinking. The only numbers $n$ can be are $n=0,1,2,3,4$ If I proceed to calculate mod 5 for each other those number I ...
1
vote
1answer
24 views

$a \equiv b$ (mod $p$) implies $a^{p^n} \equiv b^{p^n}$ (mod $p^n$)?

Let $p$ be a prime number. If $a \equiv b$ (mod $p$), does that imply $a^{p^n} \equiv b^{p^n}$ (mod $p^n$)? I think the answer will be yes, and I suspect that the way of proving it will involve ...
1
vote
0answers
23 views

Non-Linear Diophantine Equation in Two Variables [duplicate]

How many solutions are there in $\mathbb{N}\times \mathbb{N}$ to the equation $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{1995}$ ? I could solve till I got to the point where $1995^2$ is equal to the ...
2
votes
1answer
48 views

Isomorphic multiplication tables for $\mathbb{Z}/p\mathbb{Z}$

Two (undirected) multiplication graphs $n$, $m$ for $\mathbb{Z}/p\mathbb{Z}$ look the same ($n \sim_p m$) when $$a n= b\operatorname{mod} p \ \ \text{ iff }\ \ b m = a \operatorname{mod} p$$ for ...