We’re rewarding the question askers & reputations are being recalculated! Read more.

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

Filter by
Sorted by
Tagged with
67
votes
7answers
10k views

Why $9$ (and $11)$ are special in testing divisibility by digit sums? (casting out nines & elevens)

I don't know if this is a well-known fact, but I have observed that every number, no matter how large, that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until ...
1
vote
0answers
8 views

Condition $ S (S (n)) $ problem

For any natural number, let $S(n)$ denote sum of digits of $n$. Find the number of $3$ digit numbers for which $S(S(n)) = 2$. Attempt: clearly it is easy to see that the numbers which satisfy $S(S(...
1
vote
1answer
225 views

Casting nines and elevens in other bases (radix) and doing check sums for binary

I was showing my son how to cast out nines the other day. He noted that based on the way it worked, we should be able to cast out 7s when we work with octal. We tested this in several bases and it ...
0
votes
3answers
17 views

Modulo values of indivisible numbers [duplicate]

Given is prime number $p$ and natural number $a$ which is relatively prime to $p$. Prove that no numbers from the set $B={0a,1a,2a,...,(p-1)a}$ give the same value after divison by $p$.
0
votes
4answers
52 views

Prove divisibility test: $\ 7\mid10b+a\iff 7\mid b-2a$

I am currently helping a friend with their problem sheet. They have been given the question Let $n\in\mathbb{N}$ have digits $a_r, \dots a_1,a_0$, so that $$n=10^ra_r+\dots+10^2a_2+10a_1+a_0 = 10b+...
4
votes
4answers
4k views

Show that an integer of the form $8k + 7$ cannot be written as the sum of three squares.

I have figured out a (long, and tedious) way to do it. But I was wondering if there is some sort of direct correlation or another path that I completely missed. My attempt at the program was as ...
4
votes
2answers
63 views

Proving a subring of $\Bbb Z[\zeta_{11}]$ is PID

Check if $\Bbb Z[\zeta_{11}+\zeta_{11}^{-1}]$ is PID where $\zeta_{11}$ is primitive $11$-th root of unity. I don't know how to proceed? Are there any techniques in algebraic number theory to tackle ...
1
vote
2answers
762 views

Number of solutions to congruences

Is there any general form to determine the number of non-congruent solutions to equations of the form $f(x) \equiv b \pmod m$? I solved a few linear congruence equations ($ax \equiv b \pmod m$) and I ...
0
votes
2answers
135 views

The number of solutions of $x^{22} \equiv 2(mod23)$ has-

Possible answers- a).no solutions. b).$23$ solutions. c).exactly one solution. d).$22$ solutions. Solution: Since,$gcd(1,23)=23$ divides 2,so it has exactly one solution. It seems i'm wrong ...
0
votes
0answers
34 views

Proof using equation that if P an odd prime then there is a primitive root of p^n

I am currently studying Number Theory at the undergraduate level. In my textbook, I have come across the following question: Show that if p is an odd prime and n is a positive integer, then there is ...
3
votes
2answers
42 views

Proof explanation: If $p$ is prime, then $x^2 \equiv 1 \:(\mathrm{mod}\:p) \Leftrightarrow x \equiv \pm1 \:(\mathrm{mod}\:p)$

I was asked to prove the following theorem: Let $p$ be prime. Then for any $x$, the following holds true: $x^2 \equiv 1 \:(\mathrm{mod}\:p) \Leftrightarrow x \equiv \pm 1 \:(\mathrm{mod}\:p)$ My ...
0
votes
2answers
64 views

Why is $n(n+1)$ is congruent to 0,1, or 2 modulo 5?

I am trying to understand the following proof: Show that the difference of two consecutive cubes is never divisible by 5. For any integer $n$, we have $(n + 1)^3 − n^3= 3n(n + 1) + 1$, and it is ...
3
votes
4answers
541 views

Multiplicative Inverse Question

What is the multiplicative inverse of $9\pmod{37}$? I've done the Euclidean algorithm and found the gcd is $1$. I'm stuck on using the extended Euclidean algorithm. I'm confused because I'm left with $...
0
votes
1answer
41 views

What can primes (except 2,3, or 5) be congruent to (mod 30)?

I know that $30$ must divide $p-x$ which implies 30n+x=p. My thought was to find all integer solutions of this equation. I have that $0,p$ is always a solution so my next thought is to solve this ...
2
votes
1answer
35 views

Double headed arrow

I am trying to read through the paper Explorations into Knot Theory: Colorability by Rex Butler et al. (2001) and I absolutely cannot grasp the language they are using. I am hopeful that I will ...
1
vote
1answer
42 views

Congruences of consecutive Fibonacci numbers

Question: Prove or disprove that if $m$, $n$ aren’t successive Fibonacci numbers, then $$F_k\equiv m\pmod{p},$$ $$F_{k+1}\equiv n\pmod{p}$$ has solutions for only finitely many primes $p$. This is ...
1
vote
0answers
30 views

Misunderstanding with eigenvalues in $\mathbb F_2$

Suppose we have a matrix $A$ with entries in $\mathbb F_2$. Let $p_1(\lambda)$ be the characteristic polynomial of $A$ and $p_2(\lambda)$ be the characteristic polynomial of $A^2$, both of which are ...
0
votes
2answers
16 views

How to do modular arithmetic with a negative n [duplicate]

Playing with Python and the mod operation I encountered that (5 % -3) = -1. This is confirmed by WolframAlpha, and I have not been able to find any simple explanation for this online, mostly because ...
2
votes
1answer
31 views

Prove that if $P = 2^m + 1$ is a prime then $Prob((g^x \bmod P) \bmod 2 = x \bmod 2) = \frac{1}{2}$.

I'm taking a cryptography class and this algebra problem was posed as optional homework: Prove that if $P = 2^m + 1$ is a prime and $g$ is a generator of its multiplicative group then $Prob((g^x \...
4
votes
6answers
926 views

Fast Way of Finding The Remainder

I have the following question: Find the remainder of $29\times 2901\times 2017$ divided by $17$ I already have the answer (7) for this problem. I solved it using the long way by ...
2
votes
5answers
284 views

Is there a method to calculate large number modulo?

Is there a (number theoretic or algebraic) trick to find a large nunber modulo some number? Say I have the number $123456789123$ and I want to find its value modulo some other number, say, $17$. ...
-2
votes
4answers
48 views

$(-4339 \cdot 8559) \text{ mod } 43$ without calculator

How can one calculate $(-4339 \cdot 8559) \text{ mod } 43$ without a calculator? I know that the solution is 8, but just because i used a calculator. What is the correct way when trying to calculate ...
-1
votes
4answers
40 views

Solving system of Congruences with Two Variables (x and y) [on hold]

I know a bit about the Chinese Remainder theorem but what do I do in the case I was asked to solve a system of congruences such as this with two variables: $3x + y = 7$ (mod 8) $4x + 3y = 1$ (mod 8)
3
votes
5answers
242 views

How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$?

How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$? THOUGHTS: This is equivalent to say that $$ n^2 +5n + 16=0\pmod{169} $$ has no solutions. One can also observe ...
2
votes
0answers
14 views

What is U(1)/Z2 isomorphic to?

Probably a very easy question but I can't seem to figure it out: What is the group $\frac{U(1)}{\mathbb{Z_2}}$ isomorphic to? My intuition is telling me to use the homomorphism theorem, so I want to ...
0
votes
0answers
20 views

Why the Discrete Logarithm Problem in under a prime modulo

The Discrete Logarithm problem is formulated as: $\beta \equiv \alpha ^{x} \quad mod \,\, p$ where $\beta$,$\alpha$ are integers and $p$ is a prime number. Why is important that $p$ is a prime ...
2
votes
3answers
191 views

Elegant way to prove congruence

I'm stuck with the last question of this exercise 1) First question asks to solve the linear diophantine $$143x-840y=1$$ based on the remark $143\times 47 - 840 \times 8 = 1$ (done) 2) second ...
0
votes
1answer
22 views

Null Space Modulo A Non-Prime Integer

Suppose I have some matrix $A$. I can find the null vectors of $A\mod3$ and $A\mod5$ in the math software that I use, but when I try to find the nullspace of $A\mod15$ I am given the error that the ...
-1
votes
2answers
55 views

Congruence theory for divisibility statement [duplicate]

$27|2^{5n+1}+5^{n+2}$. For $n\ge1$, use congruence theory to establish that
2
votes
2answers
58 views

Why are the elements of the Cyclic Group with Generator $\langle 3 \rangle$ in $\mathbb{Z_{15}}$ {0, 3, 6, 9, 12} and not {1, 3, 9}

I'm going through Charles Pinter's A Book of Abstract Algebra which was recommended as an simple introduction. In the Chapter about Cyclic Groups he mentions that the cyclic subgroup generated by $\...
0
votes
3answers
41 views

Field homomorphism $\mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/5\mathbb{Z}$

I'm supposed to look for a field homomorphism $f: \mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/5\mathbb{Z}$. I started at $f(1) = 1$ which has to be true, due to the definition of a field homomorphism, ...
0
votes
2answers
36 views

Modulus algorithm for finding a*b^c mod n, avoiding large numbers?

I know the algorithm finding $ (a^b) mod\;n $ avoiding large numbers so I can code it, but I'm wondering if anyone can help me with a similar algorithm for $$ (a\cdot b^c )mod\;n $$ It's quite hard ...
3
votes
2answers
39 views

Prove $N_n \equiv\frac{n(n+1)}{2}\mod 9$

Prove $$N_n \equiv\frac{n(n+1)}{2}\mod 9$$ where $N_n$ is the number obtained by writing 1 to n one after the other. For example, $$N_{12} = 123456789101112$$ My Attempt: First, I listed the first ...
17
votes
3answers
4k views

Solving linear congruences by hand: modular fractions and inverses

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding $...
1
vote
2answers
35 views

Modular Arithmetic Question (Rosen Discrete Mathematics and its applications)

I came across this exercise in Rosen Discrete Mathematics and its applications and even after spending an hour plus googling I couldn't find an answer that could explain how this question is to be ...
0
votes
3answers
184 views

Euler's Formula application for distinct odd primes with gcd 1

I am looking at the following question from my undergraduate Number Theory textbook: Show that if p,q are different odd primes, and if gcd(p,q)=1, then a$\Phi$(pq)/2 $\equiv$ $1$ mod $pq$. So far, ...
-2
votes
2answers
70 views

Find the inverse of 105 mod 4 [duplicate]

I did: $$105 = 4*26+1\\ 1 = 105*1-4*26$$ So the inverse should be 5 as it is $\equiv 1 \pmod 4$ but it's 1. Why?
1
vote
2answers
55 views

Finding the inverse of 84 mod 5

I did: $$gcd(84,5) = \\ 84 = 5*16+4 \\ 5=4*1+1$$ $$4 = 84-5*16 \\ 1 = 5-4*1 \\ 1 = 5-(84-5*16)\\ 1 = 17*5-1*84$$ So the answer should be $1$ but it's 4, what went wrong?
0
votes
1answer
44 views

Determining which properties of congruences are true if $a \equiv b \pmod{n}$

I need some help, to figure out which of these propositions are true. Example of how I tried with (a): a=b (mod 10)-> m|(a-b) which is a mod m = b mod m. So a in this exercise is wrong?
3
votes
2answers
235 views

How to prove that $364 \mid n^{91} - n^7$?

I am trying to prove this statement which is equivalent to show $n^{91} = n^7 \pmod{ 364}$. By splitting modulus theorem $n^{91} = n^7 \bmod 91$ and $\bmod 4$. Then I don’t know what to do next... Can ...
1
vote
2answers
32 views

Showing that the Fermat number $F_j$ divides $F_k - 2$, where $0 \le j \lt k$

I have been instructed to solve this problem, at least in part, by showing that $F_k\equiv 2\pmod {F_j}$. I started out thus (edited to include tentative solution): $$2^{2^j}+1\equiv 0\pmod {F_j}$$ $...
1
vote
0answers
37 views

Why are modulo inverses important and what do they represent exactly? [duplicate]

I know how to get them (extended Euclidean algorithm using the mod and the number you want the inverse of if their gcd is 1, the inverse is the number you get * the one you have in the linear ...
0
votes
2answers
34 views

Two's complement signed integers modulo $n$ lacks inverse for $-32768$: does addition still work?

I have a computer program that needs to do addition using the int16_t type, i.e., signed 16-bit integers. Since this is a signed binary number, the largest ...
0
votes
0answers
23 views

Goldbach Conjecture related modular arithmetic problem

The modular arithmetic problem is related to the construction of a certain integer $\delta$ for some given $n$ such that $n \pm \delta$ are both positive primes. The problem is: We will say $X \equiv ...
1
vote
4answers
62 views

Find $4x \equiv 7 \pmod{15}$ and $3x \equiv 5 \pmod{16}$ (different exercises)

This is how I solved each: $$4x \equiv 7\pmod {15} \\ 4x - 7 \equiv 0\pmod{15} \\ 4x-7 = 15k \Leftrightarrow 4x-15k= 7 \\ $$ $$15 = 4*3+3 \\ 4=3*1+1\\ 3=3*1+0$$ $$1 = 4-3*1 \\ 3 = 15-4*3 \\ 1 = 4 -...
-2
votes
2answers
56 views

Proving Wilson’s Theorem [closed]

I’m trying to prove Wilson’s theorem while using b) statement below: Let $p$ be an odd prime. (a) Prove that $x^2\equiv 1 \pmod p$ if and only if $x\equiv \pm1 \pmod p$. (b) Let $[a]\in\mathbb ...
4
votes
2answers
446 views

Wilson's theorem, $(p-2)! \bmod p$ and $(p-3)! \bmod p$

According to Wilson's theorem, when $p$ is prime $$(p-1)! \equiv p-1 \mod p$$ What's the remainder in cases of $$(p-2)! \mod p$$ or $$(p-3)! \mod p$$ Can these be solved using Wilson's theorem ...
14
votes
5answers
10k views

Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
1
vote
0answers
15 views

recursive proof for a congruence relation lemma

The result I am trying to prove: $$n-m \Biggl\lfloor \frac{n}{m} \Biggr\rfloor =1 \Leftarrow\Rightarrow n^k\equiv 1 (\operatorname{mod} m)\quad \forall k \in \mathbb N \land n,m \in \mathbb N \,\...
0
votes
0answers
33 views

encrypt a value using public key in RSA

I'm trying to determine the ciphertext when the message 103 is encrypted using the public key (7, 143). Since C=103^7(mod 143) it can split into C = 103^7 (mod 11) C = 103^7 (mod 13) Can ...