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

1
vote
0answers
27 views

Dividing every term in congruence

Suppose we have the following congruence $6^{6^{6^{6^{6^{6}}}}} \equiv x$ (mod $10^6$). I have read somewhere that it is possible to divide this congruence by $2^6$ to get the following: $\frac{6^{...
0
votes
1answer
28 views

Writing of congruences with negatives

I am wondering if the following two congruences are equivalent: $(-2)^{56} \equiv 128^8 \equiv 3^8$ (mod $125$) and $(-2)^{56} \equiv (-128)^8 \equiv (-3)^8$ (mod $125$). The following property ...
-1
votes
0answers
21 views

For which values this very large number is divisible by 11? [on hold]

This is a question from my Discrete Maths exam: For which values of "d" digit this number is divisible by $11$? The number is: $$3d4d793243^{34243ddd3443}-9$$ Thanks for helping, i can't really ...
2
votes
1answer
35 views

Which primes divide $x^2-5$?

Which primes divide $x^2-5$? What I have tried: If $p$ divides $x^2 -5 $ then: $$x^2= 5\pmod{p}$$ Therefore, from Euler's extended theorem we get that for primes s.t $\gcd(5,p)=1$ (which are all ...
3
votes
0answers
19 views

All interval sequences mod integers

In music, an all-interval twelve-tone sequence is a sequence that contains a row of 12 distinct notes such that it contains one instance of each interval within the octave, 1 through 11. The more ...
1
vote
1answer
19 views

How to work out modular arithmetic quickly for cryptography

I am not so good at Mathematics so please kindly forgive my stupidity. Basically, I am learning modular arithmetic for cryptography and so I am struggling in understanding how to do big modular ...
1
vote
0answers
31 views

Modulo computing without Euler's theorem

How would one compute the following congruence without applying Euler's theorem(since it is not possible anyway) and without using calculator? $2^{1150} \equiv x $ (mod $5^6$)
0
votes
1answer
19 views

Modular Exponentiation with unknown base

Consider $x^a\equiv1 \pmod n$. Is there a general way to solve for $x$, given $a$ and $n$? Would knowing the factorization of $n$ make it easier?
0
votes
1answer
27 views

Modulo of a power of a power of a power

I have a question related to a modular exponentiation. My question is this: let a equal $8*12^\frac{{3^{9998}-3}}{2}$. Let b equal $8*12^\frac{{3^{a-2}-3}}{2}$. Finally, let c equal $8*12^\frac{{3^{b-...
2
votes
3answers
64 views

Find the last two digits of $2019^{2019}$

Find the last two digits of $2019^{2019}$ I know that you can typically find the last two digits of a number to any power by reducing the number to end with a one and so on (I will show an example of ...
0
votes
1answer
22 views

Last digit of power explanation

This question follows up on an example from brilliant.org Look at the example of finding the last three digits of $4^{2^{42}}$ Euler's totient function is used, but I think incorrectly so I want to ...
3
votes
1answer
30 views

Modulo calculation

I am stuck on this modulo calculation: $$718^{143} \pmod{1260}$$ I have tried using the Euler totient function with no success ($\phi(1260) = 288)$. I think I could solve it using the Chinese ...
1
vote
1answer
26 views

How can we solve $x^a = b \; mod \; n$ equation for big n, a,

I would like to have a method to solve an equation of the type: $x^a = b \; mod \; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 \times n_2 \times ... \times n_k$ I ...
0
votes
0answers
36 views

$l^2d \equiv 0,1$ (mod $4$) $\Rightarrow d \equiv 0,1$ (mod $4$)

Simple question, but it needs some introduction: Let $G$ be a finite Group of order $n$. Let $m$ be the number of conjugacy classes of $G$. A conjugacy class $C$ is called real if $C = C^{-1}$ and ...
1
vote
1answer
25 views

$D := (-1)^{\frac{m-1}{2}}n$ and $N := (-1)^{\frac{n-1}{2}}n$. Show that $N = D$.

Let $m,n$ be an odd, positive integer: $D := (-1)^{\frac{m-1}{2}}n$ with D $\equiv 1$ (mod 4) $N := (-1)^{\frac{n-1}{2}}n$ with N $\equiv 1$ (mod 4) Show that $N = D$: What I got so far: $D = \pm ...
1
vote
1answer
34 views

Quadratic congruence modulo composite number

I am trying for a given N to find the largest a ( $ 1 \leq a < N$) such that $a^2\equiv a\pmod N$ It doesn't need to be a direct formula, I can use some programming too. N can be no bigger than ...
0
votes
0answers
23 views

How to find modulo of negative floating point number?

I'm studying Hill Cipher and I tried to calculate the key. here's the problem The problem is I get -ve floating point numbers. How can I get the mod 26 of them? For example, what's the value of (-11/...
2
votes
1answer
31 views

How many integers of $ m $ digits are equal to the sum of the $ m $ -th powers of their digits in the interval $[1, …, 10 ^ 7]$?

I was checking the following number theory excercise: The number $1634$ has an interesting property. This 4-digit number satisfies that the sum of the fourth powers of its digits gives the same ...
2
votes
2answers
45 views

The quotient set $\mathbb{Z}/{\sim}$ where $a\sim b \iff$ $a^3 \equiv b^3 \pmod{7}$

Consider equivalence relation $\sim$ on $\mathbb{Z}$ s.t. $\forall a,b\in \mathbb{Z}$: $$a\sim b \iff a^3 \equiv b^3\!\!\!\! \pmod{7}.$$ There are some questions, but I am struggling with: determine ...
-1
votes
1answer
78 views

Find remainder when $8^{13^{48}}$ divided by 1000 [on hold]

Find the remainder when $8^{(13^{48})}$ divided by $1000$. First I use $\phi$ function properties but stuck how can I do? Remark : $\phi (1000)$ is relative prime that lower than $1000$ and is ...
4
votes
2answers
57 views

Alternative proof that $U(n^2-1)$ is not cyclic for $n>2$.

I'm reading "Contemporary Abstract Algebra," by Gallian. This is Exercise 4.84 ibid. and I want to solve it using only the tools available in the textbook so far. (A free copy of the book is ...
0
votes
1answer
60 views

Relatively prime numbers and probability.

Let's assume p1 and p2 are even numbers(p1≠p2) and gcd(p1,m)=1, gcd(p2,m)=1, where m is a positive integer, prove that there exist infinitely many m so that gcd(p1+m,p2+m)=1. m,m^2,...,m^k are ...
1
vote
4answers
49 views

Is $a$ or $b \equiv 0 \pmod{5}$ if $a^2-b^2 \equiv 0 \pmod{5}$? [on hold]

I have this question, knowing the last in title can i define that at least a or b is divisible by 5?
0
votes
1answer
32 views

How do we find all possible values of $a$?

$$2a5b \equiv 0 \mod 15$$ How do we find all possible values of $a$? Here I tried to divide both sides by 2 and 5 respectively $$ab \equiv 0 \mod 15 \implies a \in \{3,6\}, b \in \{0\}$$ However, ...
2
votes
6answers
42 views

Calculate $100^{1207} \mod 63$

I try to solve this question: Calculate $100^{1207} \mod 63$. There is the hint that i should calculate $100^{1207} \mod 7$, $100^{1207} \mod 9$, which is easy for me, but I don't see the relationship ...
3
votes
1answer
121 views

Prove that $2019^{2018}+2020$ is divisible by at least three primes.

Prove that $2019^{2018}+2020$ is divisible by at least three primes. I try to use modular arithmetic, but I believe the only prime I can find is 11. This means I have to find one more factor, but I'...
0
votes
1answer
27 views

Digits of $3^n$ in base $2$

I am trying to find some sort of pattern in the base-$2$ representation of $3^n$; in particular, I would like to find formulae for the number of ones in the binary representation of $3^n$, or at least ...
1
vote
2answers
74 views

For which prime numbers the ring $\Bbb Z_p$ has exactly two elements that satisfy $x=x^5$?

I tried to answer this question by trying to do calculations with some primes. $\Bbb Z_2$ has two elements: 0 and 1 which satisfy the request $\Bbb Z_3$ has three elements: 0,1,2. So 0 and 1 satisfy ...
3
votes
3answers
111 views

Some questions about $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$

Given the function: $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$ defined as follows $[x]_{44100} \rightarrow ([x]_{150},[x]_{294})$ Calculate $f(12345)$ - Answered A preimage of (...
0
votes
1answer
27 views

Solve a set of congruences

John is thinking of a number $n$. He's willing to tell us that the number is close to $10000$ and in binary system it ends on $101$. In $7$ and $11$ system it ends on digit $2$ and the last two digits ...
0
votes
1answer
47 views

The number of solutions to $x^k = a$ over $G$ a finite cyclic group is $\gcd(k,|G|)$

Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a \Leftrightarrow a^\frac{n}{\gcd(k,n)} = e$. I wish to show that ...
1
vote
3answers
49 views

Help on solutions of the congruence $f(x)=x^3+4x+8 \equiv 0 \pmod {15}$

I'm doing a little exercise, solve the congruence $f(x)=x^3+4x+8 \equiv 0 \pmod {15}$. I know that $15=3 \times 5$ and they are relatively prime, so I can split the congruence into: a) $f(x) \equiv ...
0
votes
1answer
41 views

Find all integers $x,y$ whose squares sum up to $c$ mod 5

Find all integers $x,y$ such that $x^2 + y^2 \equiv c \pmod{5}$. I managed to solve by trying one-by-one, but I guess there is some other way to solve this?
0
votes
0answers
27 views

Method of Proof concerning Prime Gap congruence Relation over two integer variables

$$p_n-p_{\lfloor n^{\frac{1}{m}}\rfloor^m}=0 \Rightarrow m=2$$ $$\quad\quad(\operatorname{tooth1})$$ $$p_n-p_{\lfloor n^{\frac{1}{m}}\rfloor^m}\not=0 \Rightarrow m\not=2$$ $$\quad\quad(\...
-1
votes
1answer
41 views

Primes congruent to a mod n.

Is there at least one prime p that is congruent to a mod n, where n can be any positive integer and a can be any non-negative integer less than n?
0
votes
2answers
28 views

How to reduce the congruence $(p-1)^{p-1}\equiv 2^{p-1}\pmod{p^2}$ into $p(p-1)+2^{p-1}-1\equiv 0\pmod{p^2}$?

In addition, how is $(p-a)^{p-1}-a^{p-1}\equiv -(p-1)pa^{p-2}\pmod{p^2}$ derived by binomial theorem?
1
vote
5answers
48 views

How to apply CRT to this congruence system?

$x=1 \pmod 8$ $x=5 \pmod{12}$ 8 and 12 are not coprime, I could break it to: $x=1 \pmod 2$ $x=1 \pmod 4$ and $x=5 \pmod 3$ $x=5 \pmod 4$ But what are the next steps to solve it? By the way, $...
0
votes
0answers
19 views

Showing two different moduli are same

$t$ is an integer coprime to primes $p,a,b$. $\max(pa,pb)<t<pab$ and $t'\equiv t\bmod p$ and $t'\in[-p^{1/2},p^{1/2}]$ holds. $a,b\in[p^{1/4},2p^{1/4}]$ holds. $t''\equiv ta\bmod pb$ and $t''\in[...
1
vote
4answers
49 views

Is it possible that $a^{2} - 1 \equiv 0 \pmod{m\cdot a}$ same as $a^{2} - 1 \equiv 0 \pmod{m}$?

$a^{2} - 1 \equiv 0\pmod{m\cdot a}$ same as $a^{2} - 1 \equiv 0 \pmod{m}$? Given that $a$ and $m$ are relatively prime, is it possible for the above equation to hold true? My rational behind this is ...
0
votes
1answer
29 views

Direct passage from $n$ prime to $n$ non-prime in Euler Totient Function $\Phi$

I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime. Let $n$ prime, we know $\Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^...
0
votes
0answers
12 views

Check if a solution exist for a linear congruence with possible zero variable

(AX + B) mod D = C I changed it form to AX ≡ (C-B) mod D then try to find if GCD(A,D)|(C-B) if so then a solution exist, but I think this method yields some false result when handling some zeros in ...
0
votes
3answers
33 views

Solution to $x^2 \equiv 1$ (mod $pq$), $p,q \geq 3$ primes.

Found the following piece online and got stuck: Let $p,q \geq 3$ be different primes. Show that there is an integer $x$ such that $x^2 \equiv 1$ (mod pq) with $x$ neither congruent with $1$ or $−1$ (...
1
vote
1answer
39 views

7-test and 13-test for correcting additions and multiplications

Design a seven-test and a thirteen-test for checking the correctness of additions and multiplications, based on modulo 7 and 13. Comment on the usefulness of your test. I know that we can check that ...
1
vote
0answers
31 views

How to simplify $2 q^{\frac{k-1}{2}} n^2 - \sigma(q^{\frac{k-1}{2}})\sigma(n^2)$

Let $k$ be a positive integer satisfying $k \equiv 1 \pmod 4$. Let $x \in \mathbb{N}$. Let $q$ be a prime number. If $$\sigma(x) = \sum_{d \mid x}{d}$$ is the classical sum-of-divisors function, ...
-1
votes
0answers
30 views

I have knowledge of where a collection of hours sit relative to each other on a clock. I wish to find the solution set.

So I have a collection of equations in arithmetic mod $12$. $A-C = 2$ $B-D = 2$ $C-E = 3$ $A \neq B$ $B \neq C$ $C \neq D$ $D \neq E$ $F-H = 4$ $F \neq G$ $G \neq H$ $K-M = 2$ $J-L = 3$ $...
-1
votes
3answers
44 views

To determine the remainder of the division

To determine the remainder of the division of 3302 + 7200 with 5. Is it correct if I find the remainder of the division separately for 3302 and 7200 and then add the two of the remainders?
1
vote
1answer
50 views

Power tower last digits

Can anyone solve the following problem of finding the 6th last digit from the right of the decimal representation of the following number: $6^{6^{6^{6^{6^{6}}}}}$ Essentially it means reducing this ...
1
vote
0answers
69 views

Multiplicative order of $a\bmod c^{k+1}$

I have some questions about moving from $\mathbb Z_{c^k}$ into $\mathbb Z_{c^{k+1}}$-specifically, with regard to the order of elements. Suppose $a$ (which is coprime to $c$) has multiplicative ...
6
votes
1answer
131 views

Patterns in division graphs modulo $n$

(I made an edit due to hints from Alex Ravsky. Thanks to him.) General division graphs with nodes $1,2,\dots N$ and an edge between $n$ and $m$ when $n$ divides $m$ or $m$ divides $n$ are sparse and ...
2
votes
1answer
35 views

Why must any solution of this congruence equation satisfy gcd(x,11)=1?

Solve the congruence $x^5\equiv 3 \space mod \space 11$ The solution says that any solution of this equation must satisfy gcd(x,11)=1 and I'm not sure why. I understand the theorem : "the linear ...