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

1
vote
2answers
59 views

Last 3 digits of $3^{3^{3^3}}$

I am trying to find the last $3$ digits of $3^{3^{3^3}}$, or $3^{3^{3^3}} \mod 1000$. I realized that I need to use the Euler's totient function in some way, but I was unsure on how to do it. Would ...
0
votes
0answers
38 views

Digit Modular-Arithmetic Number Theory Question

A number consists of 10-digits $d_{10}d_9\ldots d_1$ where $d_i \in \{0,1, . . . ,9\}$ and $d_1 \in \{0,1, . . . ,9, X\}$. The number is valid if: $$ \sum_{i=1}^{10} i*d_i \equiv 0 \bmod 11, $$ ...
2
votes
4answers
45 views

Show that if $m$ in $\mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$.

Show that if $m$ in $\mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$. Also, I have to work in $\mathbb{Z}/63 \mathbb{Z}^{*}$, thus the group $63$ modulo $\...
0
votes
3answers
36 views

If $x^{11} \equiv y \bmod 17$, find $k$ so that $y^k \equiv x \bmod 17$ [duplicate]

I've been trying to work through some problems on number theory and got stuck with the following question: Find an integer k so that if x and y are any integers for which x^11 ≡ y mod 17, then y^k ≡ ...
0
votes
2answers
33 views

Explanation of this example

This is in reference to Number Theory/ Modular Arithmetic. In EXAMPLE 11 in the above picture, I cannot understand the proof from the 8th line from "Therefore, there exists...". Why is there a unique $...
1
vote
0answers
65 views

Problem in understanding a proof in Number Theory

This question in the reference to Number Theory (Modular Arithmetic). I need some help in understanding the proof of Proposition 6. In the third line of the proof of Proposition 6, "$\dots 0\leq k,...
-1
votes
3answers
107 views

Help to prove that: if m ≡ n (mod a) then mb ≡ nb (mod ab)

Question asks to use mathematical language to prove that: if m ≡ n (mod a) then mb ≡ nb (mod ab). Question also says if proving an equivalence, each direction should be clear.
0
votes
2answers
24 views

Help with Complete Residue Systems

I need help with this problem: Find a complete residue system mod 17 that consists entirely of perfect squares or explain why no such complete residue system is possible. I would expect that this ...
1
vote
0answers
64 views

Is there a solution for $2^{n-1}\equiv 2^{16}+1\mod n$ or $2^{n-1}\equiv 2^{26}+1\mod n$?

Related to this question : Can I find all solutions of $2^{n-1}\equiv k\mod n$? Does one of the congruences $$2^{n-1}\equiv 2^{16}+1\mod n$$ and $$2^{n-1}\equiv 2^{26}+1\mod n$$ have an integer ...
1
vote
2answers
38 views

Help with modular congruences with powers

I need help with the second part of the following question: Suppose $x$, $y$, and $p$ are integers, $p$ is prime, and $x^2 \equiv y^2 \pmod p$. Does it follow that either $x \equiv y \pmod p$ or $x ...
1
vote
1answer
53 views

Smallest possible value [on hold]

Given that $x$ is relatively prime to $6693008$ and $x^a \equiv x^b\mod 6693008$, what is the smallest possible value for n such that $a \equiv b \mod n$? And why?
1
vote
1answer
35 views

Notation for “congruent to a member of”

Is it acceptable to write $x\in S\pmod m$ to denote "$x$ is congruent to a member of $S$ modulo $m$"? Are there any established alternatives to this notation? An example of use: "When $m\ge 5$ is ...
0
votes
2answers
46 views

Write a single congruence?

Write a single congruence that is equivalent to the pair of congruences: $x\equiv 1(\mod4)$ and $x\equiv 2 (\mod 3)$. I am new to Number Theory/ Modular Arithmetic. Just started reading the ...
-1
votes
2answers
82 views

A problem of divisibility [on hold]

Say $n$ is a natural number such that $$3^n+3^{n+1}+...+3^{2n}=k^2$$ where $k$ is a natural number. Prove that $n$ is divisible by $4$.
-2
votes
2answers
51 views

Easy why to solve modular-arithmetic? [on hold]

Hey my question is about modular-arithmetic. I can solve this, but is there a easy why, formula or some kind of trick to solve this fast. $$ a\equiv b\pmod 5\iff \text{a mod b = 5} \\ a\equiv b\pmod ...
-1
votes
1answer
104 views

Find $438^{87493} \equiv ~? \pmod{11}$ [on hold]

How to find the value of '?' a mod m = b mod m , will this formula be used? I am taking discrete maths course for CS. And this question is from one of its chapter
1
vote
0answers
23 views

Real Modulo Numbers in the Interval [0, 1), and Multiplication of

Let's say we have a real number, A, in the interval [0, 1). If we add another real number to it, it "Wraps" around back to zero. So, for example: Lets say: A = 5/13 If we multiply A by 2, we get: ...
2
votes
2answers
88 views

Number Theory: Problem with proofs

There are two propositions in the chapter of Number Theory in my book, the proofs of which I am having trouble to understand. For Proposition 3 I cannot understand the proof from "Therefore ..." in ...
3
votes
6answers
68 views

Prove without induction that $2×7^n+3×5^n-5$ is divisible by $24$.

I proved this by induction. But I want to show it using modular arithmetic. I tried for sometime as follows $$2×7^n-2+3×5^n-3\\ 2(7^n-1)+3(5^n-1)\\ 2×6a+3×4b\\ 12(a+b)$$ In this way I just proved ...
0
votes
0answers
42 views

Bob has a public key $(e, n)$ with $n= 55125947$. We know that the primes, $p$ and $q$, that Bob chose to determine $n$ are both greater than 20.

Bob has a public key $(e, n)$ with $n= 55125947$. We know that the primes, $p$ and $q$, that Bob chose to determine $n$ are both greater than 20. Prove that $(p-1)(q-1)/pq>0.9$ You intercept 7 ...
0
votes
1answer
58 views

What does $5\mathbb{Z}_{25}$ mean? (Notation help)

Does $5 \mathbb{Z}_{25}$ refer to the numbers in $\mathbb{Z}_{25}$ multiplied by $5 $ -- i.e., there are 25 elements -- or does it refer to multiples of $5$ in $\mathbb{Z}_{25}$ -- i.e., there are $5$ ...
6
votes
0answers
50 views

Prove that $1980^{1981^{1982}}+1982^{1981^{1980}}$ is divisible by $1981^{1981}$. [duplicate]

I am stuck with this hard proof question. It is: Prove that $1980^{1981^{1982}}+1982^{1981^{1980}}$ is divisible by $1981^{1981}$. I don't know how to start, except that modular arithmetic is ...
2
votes
2answers
95 views

Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.

Suppose that $p$ and $q$ are distinct primes and that $m$ is an integer satisfying $\gcd(m, pq) = 1$. Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove ...
0
votes
1answer
30 views

Inverse of a equation with modulo operator

I have this equation: $y=ax+b \quad \pmod{26}$ where a, b are two parameters. I would like to calculate the inverse of this equation, but I don't know which algebra rules I have to apply. Can you ...
5
votes
3answers
891 views

Largest multiple of $7$ lower than some $78$-digit number?

What I am trying to achieve, is related to cryptography/blockchain/bitcoin . So, the largest number here is huge, in other words: I want to find the largest multiple of 7, which is lower than this ...
0
votes
1answer
34 views

Solving $2x^{3}=3$ over $\mathbb{Z}_5$.

Really new to dealing with $\mathbb{Z}_n$. I'm trying to calculate $2x^{3}=3$ over $\mathbb{Z}_5$. I did a similar question - solving $3x^{2}+x+1=0$ over $\mathbb{Z}_5$: $$3x^{2}+x+1=0 \\\...
2
votes
6answers
88 views

Computing last two digits of $27^{2018}$

For abstract algebra I have to find the last two digits of $27^{2018}$, without the use of a calculator, and as a hint it says you should work in $\mathbb{Z}/100\mathbb{Z}$. I thought breaking up ...
0
votes
0answers
33 views

Is it possible for $a = 2$ mod $17$ to be a Fermat non witness for $n = 85$?

Let $n = 85$. Suppose that an element $a \in (\mathbb{Z}_n)^*$ satisfi es the relation $a = 2$ mod $17$. Is it possible for such $a$ to be a Fermat non witness for $n = 85$? So a Fermat non witness ...
1
vote
3answers
82 views

Using Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse — Need some help understanding the solutions here.

The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm. a. $8^{-1}\bmod17=8^{17-2}\bmod17=8^{15}\bmod17=15\bmod17$ b. $5^{-1}\bmod23=5^{...
0
votes
1answer
26 views

If $(\alpha,\beta)$ is the factor pair congruences of algebra $\mathbb{A},$ ia $(\forall \gamma\in ConA)\alpha\circ\gamma=\gamma\circ\beta?$

Let $\mathbb{A}$ be an algebra such that $ConA$ is the distributive lattice. If $(\alpha,\beta)$ is the factor pair congruences of algebra $\mathbb{A},$ prove that $(\forall \gamma\in ConA)\alpha\circ\...
0
votes
1answer
135 views

Determine the remainder when $7^{7^{2019}}$ is divided by 47.

Determine the remainder when $7^{7^{2019}}$ is divided by 47. 47 is prime, perhaps we can do something with that? I'm not sure how to approach this question, any and all help is appreciated. Thanks!
1
vote
1answer
37 views

Pattern in power towers of 2 involving last digits

We have \begin{align} 2^{2^{2}} &\mod 10 = 6 \\ 2^{2^{2^2}} &\mod 100 = 36 \\ 2^{2^{2^{2^2}}} &\mod 1000 = 736 \\ 2^{2^{2^{2^{2^{2}}}}} &\mod 10000 = 8736 \\ 2^{2^{2^{2^{2^{2^2}}}}} &...
1
vote
1answer
21 views

One homomorphism to another in group under addition

Let $n \geq 2$, and let $G = \mathbb{Z}/n\mathbb{Z}$, which is a group under addition. There is a function $\phi_{\bar{a}}(\bar{x}):G \rightarrow G$ for every $\bar{a} \in G$, with $\phi_{\bar{a}}(\...
0
votes
1answer
44 views

Relations between $k, t$ and modulo $n$

Suppose we have $n$ people in a circle $\{0, 1, ..., n-1\}$ Also, suppose we have another person who goes around said circle and gives each of the $n$ people a gift, one each $k$ people, so: \begin{...
-4
votes
3answers
64 views

$\iota \equiv \pm 3, \pmod{10}$

I was reading up on the properties modulo function, when I saw the property: $$-a \equiv (10-a) \space \pmod{10}$$ Which means $$-1 \equiv (10-1) \equiv 9 \space \pmod{10}$$ Now: $$\iota = \sqrt{-...
2
votes
1answer
43 views

How to derive the relation between $k$ and $l$ given $\langle g^k \rangle = \langle g^l \rangle$ in a cyclic group $C_n = \langle g \rangle$?

It is known that For a cyclic group $C_n = \langle g \rangle$ of order $n$, we have $\langle g^k \rangle = \langle g^{(k, n)} \rangle$, where $k \in \mathbb{Z}$. I am able to verify this result. ...
1
vote
1answer
61 views

Find all positive integer $n$ such that there exist $m\in\mathbb{Z}$ with $2^n-1|m^2+9$

I have an problem with elementary number theory: Find all positive integer $n$ such that there exist $m\in\mathbb{Z}$ with $2^n-1|m^2+9$ It's look like the problem in this link, but there some ...
2
votes
2answers
114 views

Can I find all solutions of $2^{n-1}\equiv k\mod n$?

Suppose$\ k\ge 2\ $ is a positive integer. Can I find all positive integers $\ n>1\ $ with $$2^{n-1}\equiv k\mod n$$ ? I only found out yet that there is always a solution if $\ k>2\ $ and $\...
-2
votes
1answer
53 views

Number Theory - Modular Arithmetic [duplicate]

How would you do this problem? The equation $x^2 \equiv 1 \bmod 493$ has two obvious solutions: $x \equiv \pm1 \bmod 493$. Using that $x \equiv 86 \bmod 493$ is another solution to find a ...
2
votes
1answer
52 views

Noninvertible matrix mod s from an invertible matrix

Let $A\in M_2(\mathbb{Z})$ with nonzero determinant. Show that there exist infinitely many numbers $s\in\mathbb{N}$ such that $$ \exists a_s\in\mathbb{N}^*:A^{a_s}-I \equiv O\mod s. $$ My attempt is ...
0
votes
0answers
25 views

How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?

A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
1
vote
1answer
69 views

Do there exist super-Wieferich primes?

A Wieferich prime is a prime $p$ such that $2^{p-1}\equiv 1\mod{p^2}$. Denote the order of $2$ modulo $p$ by $O(p)$. Then we can show that a prime $p$ is a Wieferich prime if and only $O(p^2)=O(p)$. ...
1
vote
3answers
33 views

Prove that $k|φ(m)$ [duplicate]

Suppose $a$ and $m$ are relatively prime and $k$ is the smallest natural number that $a^k\equiv1\mod m$. Prove that $k|φ(m)$. This is just a variation of Fermat Theorem, So do I just need to show ...
0
votes
4answers
38 views

Prove if p is a prime number that does not divide a, then $a^{p^2}$ congruent to $a^p\mod p^2$

I tried to do proof by contradiction, so I started to do use real arbitrary numbers. I decided I use p for prime still, but a being a multiple of p and by doing this, the statement is still true. I ...
1
vote
1answer
21 views

Congruence class to show that $[a]_8 \neq [b]_8$

Let $f : \mathbb{Z}_8 \rightarrow \mathbb{Z}_2 \times \mathbb{Z}_4$ be defined by $f([m]_8)=([m]_2,[m]_4)$ for $m \in \mathbb{Z}$ (assuming that $f$ is well defined). Find integers $a$ and $b$ such ...
2
votes
1answer
83 views

How to elegantly find the remainder of $en$ divided by $n+1+\frac{n-1}{d}$

Motivation: Let $n,e,d$ be positive integers greater than 2, such that $e\mid n-1$ and $d\mid n-1$. Denote $N=en$, $M=n+1+\frac{n-1}{d}$. Find $q,r\in \mathbb{Z}$ such that $$N=qM+r, 0\le r < ...
1
vote
2answers
40 views

Using Chinese Remainder Theorem for large modulo

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem: Compute which element of $\mathbb{Z}/2550\mathbb{Z}$ under the map of the Chinese ...
1
vote
1answer
44 views

When $p<q$ there is a solution to $qx+py = c$, but not when $p>q$. Why?

For linear diophantine equation: $qx+py = c$ , where $p$ is a prime and $q$ is a natural number, why is it that if $p<q$ then there is a solution to the equation, however when $p>q$ then there ...
2
votes
1answer
45 views

Find the remainder when $(34! + {75}^{37})^{39}$ is divided by $37$

Since Fermat Theorem is $a^{36} \equiv 1 \mod {37}$, ${75}^{37}$ becomes ${75}^{36} \times 75$ and in $\!\!\mod {37}$ they both become $1$. I have $(34! + 1)^{39}$. I do the same again with $(34! + ...
0
votes
0answers
30 views

For all $[a]$,$[b]\in{\mathbb{Z}m}$, if $[a][b]=[0]$, then $[a]=[0]$ or $[b]=[0]$. Prove that if $S$ is true, then $m$ is prime.

Let $m\in{\mathbb{N}}$ such that $m>1$. Consider the implication $S$: For all $[a]$,$[b]\in{\mathbb{Z}m}$, if $[a][b]=[0]$, then $[a]=[0]$ or $[b]=[0]$. Prove that if $S$ is true, then $m$ is prime....