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

learn more… | top users | synonyms

4
votes
2answers
389 views

What will be the one's digit of the remainder in: $\left|5555^{2222} + 2222^{5555}\right|\div 7=?$

What will be the ones digit of the remainder in: $$\frac{\left|5555^{2222} + 2222^{5555}\right|} {7}$$
0
votes
1answer
72 views

Congruence with variable modulus

I have been working on some problems and one of them has been particularly challenging. The problem is as follows. Find a non-trivial (meaning more than 1 digit) positive integer a that satisfies: ...
3
votes
2answers
127 views

How to solve $ x = 5^{1345}\bmod 58$? Fermat's little theorem

$ x = 5^{1345}\bmod 58$. I wrote a program that finds and period of residues and builds a table. This table consists of $k$ lines where $k$ is a number of residues in one repeating block, as residues ...
0
votes
1answer
156 views

Modular arithmetic: mod p-1 after exponentiation?

I keep coming across proofs that seem to use the following derivation, but I'm unsure where it comes from. What theorem shows that this is a correct step to take? $ g^{x} = g^y$ mod $p$ $\iff$ $x = ...
1
vote
3answers
88 views

If $n_1$ divides $(a-b)$ and $n_2$ divides $(a-b)$, then $lcm(n_1,n_2)$ divides $a-b$

I was reading elementary number theory when I came across the theorem that $ a≡b \pmod{N}$ and $N=nm$ implies that $a\equiv b\pmod{m}$. And as a consequence of it, $a ≡ b \pmod{r}$ and $a \equiv b ...
0
votes
1answer
91 views

integer transform

Let be $X$ an integer set: $X=\{0,1,2,\ldots,63\}$. Let be $(x,y)$ two elements from $X$ ($(x,y)\in X \times X$). I want to know if exist two transforms $T_1 :X \times X \to X$ and $T_2 :X \times X ...
1
vote
3answers
232 views

Question about rings and modulo multiplication tables

Why is 2=0 in K for part a)? Also I don't understand what part b) is asking you to do - what does it mean by alpha = [X], so M=etc. Could someone please explain the question and the solutions to part ...
2
votes
1answer
111 views

Solving system of quadratic congruences

If you have a system ex: $ab \equiv 1 \mod 9$ $ab \equiv 3 \mod 10$ $ab \equiv 10 \mod 11$ $ab \equiv 7 \mod 12$ is there a way to determine integers $a$ and $b$?
5
votes
1answer
530 views

Modulo complex number

I was wondering what would happen if we tried to do a modulo operand with complex numbers? For instance, what would be the answer (if any) to the next statement? $ x \mod (a + bi) $ can it be ...
1
vote
1answer
23 views

Proving modular implicaton

I have to prove that for $m \in \mathbb{Z_{>1}}, b \in \mathbb{Z}$ it $\exists a \in \mathbb{Z} : ab \equiv 1 (mod\;m) \Rightarrow \exists a'\in \mathbb{N}, a'<m:a'b=1 (mod\;m )$ Since we have ...
1
vote
2answers
287 views

Finding an integer that satisfies a congruence class equation

We have integers $a = 1231940$, $b = 9935$ and $n = 3999831$ and the ring $\mathbb{Z}/n\mathbb{Z}$. Now we should find an integer $x$ that satisfies the equation $[a] \odot_n [x] = [b]$. How can such ...
0
votes
3answers
249 views

Determine the number of solutions for quadratic equation modulo prime

Given that $106$ is quadratic residue $\bmod\ 139$, how can I determine the number of solutions to the following equation? $$x^2 \equiv 106 \pmod{139}$$
0
votes
0answers
57 views

Using modular arithmetic for the decimal byte ring, compute the following… [duplicate]

Using modular arithmetic for the decimal byte ring, Compute: $5 + (- 175+222)*13 = ~?$ This is a question I'm supposed to understand before I start a assembly language course next semester. Can ...
2
votes
2answers
82 views

If $p\equiv 1\pmod{8}$, then $-1$ is fourth power?

I know that $-1$ is a square modulo $p$ iff $p\equiv 1\pmod{4}$. Curious about this, I'm trying to show that $-1$ is a fourth power if and only if $p\equiv 1\pmod{8}$, for $p$ odd. I know that if ...
1
vote
1answer
182 views

GCD of two polynomials in Mod 2 [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ Let $p$ and $q$ be distinct primes. I wonder is the following statement always true? $$\gcd(x^p-1, x^q-1) ...
7
votes
2answers
243 views

$3x^2 ≡ 9 \pmod{13}$

What is $3x^2 ≡ 9 \pmod{13}$? By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way? ...
2
votes
1answer
155 views

Quickest way to find smallest positive integer solution to $ax\equiv b\mod m$

Let $I(a,b,m)$ be the smallest postive integer solution $x$ to the modular equation $$ax\equiv b\mod m.$$ What is the quickest way to find $I(a,b,m)$ for given integers $a,b,m$? I know how to find it ...
0
votes
0answers
74 views

Distribution of binary digits in moduli

Considering the (infinite) set of all positive integers that are a product of $2$ primes only, represented in binary $100...01$. Question: is the distribution of the proportion of $0,1$ digits ...
-1
votes
1answer
140 views

Compute Using modular arithmetic for the decimal byte ring,

Using modular arithmetic for the decimal byte ring, Compute: 5 + (- 175+222)*13 = This is a question I'm supposed to understand before I start a assembly ...
7
votes
3answers
333 views

Why do the gaussian integers have only 2 congruence classes mod 1+i?

If we consider $Z[i]$ modulo $1+i$, why are there only two congruence classes?
2
votes
1answer
84 views

Occurrences of a residue when reducing the multiplication table mod $a$.

Consider the following diagram of numbers. $$\begin{pmatrix}1 & 2 & 3 & 4 &.... & a \\ 2 & 4 & 6 & 8 & .... &2a \\ 3 & 6 & 9 & 12 & .... & ...
1
vote
2answers
70 views

Modular arithmetic: confusion one the $mod$ operator.

Suppose I have $a\equiv b \text{ (mod $c$)}$ and I just know $c$. I want to know, say $b$. Is this the same as $a$ mod $c$? If so, why? I think I confuse the congruence with the equality symbol, ...
1
vote
1answer
164 views

Congruence relationship used for primitive residue classes modulo n result

I'm trying to understand a proof for a theorem that states conditions under which the group of primitive residual classes modulo $n$ is cyclic. This proof uses the following result attributed to Gauß: ...
0
votes
1answer
61 views

Modular arithmetic with different moduli

What is the cheapest and fastest way to find the remainder of the modular arithmetic $\pmod {n}$ when we have the reminder for $\pmod {n-1}$ or $\pmod {n+1}$ ? As an example, if: $$ 3^{60} \equiv ...
1
vote
1answer
324 views

Proof of Wilson's Theorem using Fermat's Little Theorem

Wilson's theorem states that a natural number $n>1$ is a prime number if and only if $$ (n-1)! \equiv -1 \pmod {n} $$ Can we prove it using Fermat's Little theorem? If yes, then how?
1
vote
2answers
1k views

Finding the last nonzero digit of $30^{2345}$

3)Find the last non-zero digit of $30^{2345}$ $3^1=3$ $3^2=9$ $3^3=27$ $3^4=81$ $3^5=243$ ... as last digit is following a cycle of $4$ so $2345/4$ gives remainder of 1, and ...
2
votes
3answers
2k views

Modular Quadratic Formula

How can I solve quadratic equations using modular arithmetic? E.g. $$2x^2 + 8x + 2 = 0 \pmod{23}$$ N.b. I have changed the figures from those in my homework question because I don't want a solution ...
2
votes
3answers
48 views

Modular arithmetic help

Given fixed $a,p$ how can I show that $a^n$ mod p is never equal to a given number, for any integer n? For example how can I show that $4^n$ mod 3 is never equal to 2.
5
votes
3answers
237 views

How to compute $7^{7^{7^{100}}} \bmod 100$?

How to compute $7^{7^{7^{100}}} \bmod 100$? Is $$7^{7^{7^{100}}} \equiv7^{7^{\left(7^{100} \bmod 100\right)}} \bmod 100?$$ Thank you very much.
0
votes
4answers
159 views

Modular algebra with an non-integer solution

Suppose I was asked to solve: $$5x+6=10 \mod 17$$ I would get this far with normal algebra: $$x = \frac{4}{5} \mod 17$$ But now I have a non integer expression ($4/5$) where it does not belong. ...
0
votes
0answers
255 views

Computing square roots modulo prime powers

I am trying to implement an algorithm that can compute the square root of a quadratic residue mod a prime power. For integers $a$ such that $p\not\mid a$ $p\neq 2$ it's relatively straightforward ...
1
vote
2answers
377 views

Chinese Remainder Theorem result varies

Sorry if this question is lame. First post! I was going through this book Abstract Algebra Theory and Applications Thomas W. Judson Stephen F. Austin State University In the Chapter ...
0
votes
2answers
21 views

How to find the total no. of cards if I know the numbers left on putting them in different stacks?

I have a collection of cards, then: If I put them in stacks of 2, I have 1 left If I put them in stacks of 3, I have 1 left If I put them in stacks of 4, I have 1 left If I put them in stacks of 7, ...
0
votes
1answer
271 views

Running time of Modular Exponentiation

I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm: ...
2
votes
2answers
104 views

Basic Modular Exponentiation reasoning

I am trying to understand the modular exponentiation algorithm. Why is it that: $x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$ What is the basic reasoning behind this?
3
votes
3answers
187 views

exponentiation and modular arithmetic

How would I be able to simplify $$2^x\mod 10^9$$ Since there are only $10^9$ possible values mod $10^9$, somewhere the pattern must repeat. I could have a computer program trudge through it, but ...
2
votes
1answer
135 views

Nef divisors on the compactified modular curve level $N$

Consider the compactified modular curve with full level structure $X=\overline{\Gamma(N)\setminus \mathcal{H}}$. We know the Hodge bundle (the extension of the hodge bundle to the compactification) ...
0
votes
1answer
138 views

Fundamental Period of sequence modulo N

Let $T$ denote the smallest exponent such that $b^T \equiv 1 \pmod{N}$, then we call $T$ as fundamental period of the sequence satisfying the equation. As an example for $b=2, N=2731$ we have $T=26$ ...
1
vote
2answers
173 views

Proof on linear congruence solutions

There's a proof in a section in my book on modular arithmetic I don't really understand. On linear congruences: $ax \equiv b \text{ (mod $m$)}$ Suppose that $\gcd({a,m}) = d > 1$ and $b$ ...
2
votes
5answers
112 views

Can modulus be negative?

For example, if I compute $18 \bmod 5$, the result will be $3$. This will be because of $5\cdot3+3=18$, but can I have $5\cdot4-2=18$ which gives me $-2$?
1
vote
3answers
79 views

linear congruent modulo with only one solution

$n \cdot x ≡ k \mod{20} \\n,k \in \mathbb{Z}$ Choose $n,k$ so there is only $(a)$ one, $(b)$ no solution in $\mathbb{Z_{20}}$. If $n = 0$, then two solution exist, and that is $k=20$ and ...
2
votes
1answer
645 views

Show that Fermat's Little Theorem doesn't hold if p is not prime …

I would like to show that Fermat's Little Theorem doesn't hold when p is not prime. I'm assuming this would be a proof by contradiction that Fermat's Theorem only works with prime numbers, but I'm ...
0
votes
1answer
35 views

Efficient procedure for multiple exponentiations in a commutative group $\mathbb{G}$

Suppose $\mathbb{G}$ denotes a commutative group. Is there a way to the performance of an operation that does many modular exponentiations. That is an operation of the following type: suppose $b_1, ...
1
vote
5answers
166 views

How to prove that the number of solutions of $ x^2 \equiv a \pmod{p}$ is 0 or 2?

I want to prove that the equation $ x^2 \equiv a \pmod{p}$ either doesn't have or has 2 solutions. (p is odd prime , a is integer , a $\ne pk$ )
0
votes
1answer
82 views

How to solve $2x^3+7x-4\equiv0 \pmod{25} $ without Hensel's lemma and with it

In general how to solve this equation:(with Hensel's lemma and without it) $$2x^3+7x-4\equiv0 \pmod{25} $$
1
vote
1answer
71 views

Proving that if $xo + yp = 1$, then $\gcd(o,p) = 1\;$?

I'm currently trying to prove the equation that you see above. I know that it must have something to do with the laws of divisibility, and these rules in conjunction with rules about integers, but ...
2
votes
2answers
97 views

Repeated multiplication in modulo $n$ that eventually yields every number

Given an initial number $m$ and a modulo $n$, is there a way of determining some constant multiplier $k$ so that $(m \times k^x) \mod n$ will eventually yield all integers in $[1,n]$ by incrementing ...
0
votes
2answers
328 views

Number of solutions of $ax \equiv b \mod n$

I want to solve $ax \equiv b \mod n$ given a solution $x_0$. How can i prove that there are exactly $(a,n)$ solutions ?
2
votes
2answers
79 views

Proving that $x^a=x^{a\,\bmod\,{\phi(m)}} \pmod m$

i want to prove $x^a \equiv x^{a\,\bmod\,8} \pmod{15}$.....(1) my logic: here, since $\mathrm{gcd}(x,15)=1$, and $15$ has prime factors $3$ and $5$ (given) we can apply Euler's theorem. we know that ...
3
votes
4answers
148 views

Fermat's little theorem confusion

Problem, What is the remainder when $3^{50}$ is divided by $7$ I know I have to use Fermat's little theorem, but I'm confused at a certain point. I have that $3^{6}\equiv1 \bmod7$ Now I'm not sure ...