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
1answer
41 views

Proving that $y$ is a square mod $p$ and $-y$ is square mod $q$

Given that $p, q \equiv 3 \pmod 4$, neither $y$ nor $-y$ has a square root mod $pq$, and that $y$ is invertible mod $pq$, how would I prove that $y$ is a square mod one of $p, q$ and $-y$ is a square ...
0
votes
1answer
27 views

How to find a integer using modular arithmetic

Hi guys, I'm preparing for my maths exam in 2 weeks and these sorts of questions come up every year. Unfortunately I was out when the lecturer taught us how to do these and I looked up his notes but ...
1
vote
1answer
28 views

Finding multiples of three given a few simple rules

We were given this problem the other day and it seems a little over my head, so I thought I'd share it here for any possible advice or assistance :). The problem is as follows: Initially, $x = 1$. ...
1
vote
1answer
65 views

Preserving modulus residue under division

Modulus residue is preserved or honored (sorry, I don't know the correct term. Is it homomorphism?) under addition and multiplication. For example: 2 + 4 = 6 2 * 4 = 8 Then, making those values ...
-1
votes
0answers
29 views

Finding unknown in modular arithmetic.

I know how to work something like $19x \equiv 4 \pmod{141}$ (using the method of checking if $141$ divides $19x - 4$ when $x = 0,1,2, \ldots$), but for some reason, I don't know how to solve an ...
1
vote
1answer
43 views

Is this result correct? If so, where does it come from?

$$ a^{nr} \mod 10 \equiv (a^n \mod 10 )^r \mod{10} $$ I'm not sure if this result holds, I haven't taken any real number theory. My notation is most likely wrong however my thinking is the following ...
2
votes
1answer
23 views

Proof of $a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$

I am currently studying modular arithmetic for a course in cryptography. I have proved many operations, but I am stuck in one: Assume $n,a\in \mathbb{N}$ and $n\ge 2$. Prove that if $\gcd(a,n)=1$ ...
0
votes
0answers
17 views

How does the Chinese Remainder Theorem help breaking the Diffie Hellmann Problem?

on http://crypto.stackexchange.com/questions/30328/why-does-the-modulus-of-diffie-hellman-need-to-be-a-prime/, i asked about why the modulous in the Diffie Hellmann Key Agreetment needs to be a prime. ...
1
vote
1answer
59 views

Proof verification for FLT when $n=3$

For: $$a^3 + b^3 = c^3$$ Why can't I simply take mod 3 ? The only possibility is when $a\equiv 0$ (mod 3) and $b\equiv 0$ (mod 3) But if this happens then 3 can be taken as a common factor. ...
1
vote
1answer
12 views

Explain this step in solving this system of linear congruences.

I'm looking at this example and it doesn't make sense to me. We have to solve the following systems of linear congruences : $x\equiv 1\pmod 5$ $x\equiv 2\pmod 6$ $x\equiv 3\pmod 7$ We take ...
0
votes
1answer
16 views

Compute mean on a torus / circular domain

I have $n \in \mathbb{N}$ values lying in a real, circular domain of period $T \in \mathbb{R}^{+*}$: $(\xi_i \in [0, T[^c)_{i \in \{1,\dots, n\}}$ I refer to the domain $C_T = [0, T[^c$ as a ...
0
votes
1answer
13 views

Modular Exponentiation doesn't work on a prime mod?

For 83627264^275372 mod 277 using modular exponentiation, I noticed that things weren't lining up when I checked them on Wolfram. So far I have this: 83627264^1 mod 277 = 133 83627264^2 mod 277 = 238 ...
0
votes
1answer
24 views

Calculating time using modulus

In my textbook, the question is as follows: What time does a 24 hour clock read: a) 100 hours after it reads 2:00 b) 45 hours before it reads 12:00 c) 168 hours after it reads 19:00 And provides ...
2
votes
1answer
28 views

how do i show that $x^2+1$ divides $x^{p-1}-1$ in $\mathbb{Z}_p[x]$?

$p$ prime integer. If we are given that $p \equiv 1$ modulo $4$ then $x^2+1$ divides $x^{p-1}-1$ in $\mathbb{Z}_p[x]$. I can show this by considering the cyclic subgroup $\langle g \rangle$of ...
0
votes
0answers
25 views

Exercise about radix

Anyone can help me with this problem? Find the integers that in decimal radix the tens and units of their square are equals. $a = 2p − 1, b = 2p + 1, c = 2p + 3.$ Find $p$ that $a^2 + b^2 + c^2$ is ...
0
votes
0answers
61 views

Show that $1+X^4$ is reducible over $\mathbb Z_p$ for every prime $p$. [duplicate]

Show that $1+X^4$ is reducible over $\mathbb Z_p$ for every prime $p$. MY ATTEMPT==>I have used Fermat's theorem for this as $X^{p-1}≡1\bmod p$, then this can also be written in the form ...
0
votes
1answer
78 views

Congruence - Number Theory

Prove that $2005^{2005}$ is not the sum of two perfect cubes. I have looked at some mods but none have given me anything useful as of yet. I looked at the usual mods such as $4, 5, 7, 11, 13$ but ...
0
votes
0answers
18 views

Question regarding congruence notation [duplicate]

I have a question regarding notation in modular arithmetic and congruence classes. I am used to the notation $a \equiv b$ $(\mod n)$; it simply means n divides a-b But I've seen a similar notation ...
0
votes
2answers
28 views

Finding Large Bases with Large Exponents [duplicate]

I'm given the question to find: $151 678 213 ^{115431217}\pmod{10}$ I know that 10 is not prime, so I can't use fermats theoreom. So I've attempted using eulers totient function I know that: ...
2
votes
2answers
64 views

If primitive root modulo $mn$, then primitive root modulo $m$ and $n$

Let $a$ be a primitive root modulo $mn$. Show that $a$ is also primitive root modulo $m$ and $n$. Showing $(a,mn)=1\Longrightarrow (a,m)=(a,n)=1$ is not a problem. The problem is showing $a^{\varphi ...
0
votes
1answer
54 views

Find all the Zeros and their multiplicities of $f(x)=x^5 +4x^4 +4x^3 -x^2-4x +1$ over $\Bbb Z_5$.

Find all the Zeros and their multiplicities of $f(x)=x^5 +4x^4 +4x^3 -x^2-4x +1$ over $\Bbb Z_5$. Firstly,I've found the zeros of $f(x)$,just by simply substituting the elements of $\Bbb ...
1
vote
2answers
35 views

Prove that $40\mid 3^{4N}-1$

Prove that $40 \mid 3^{4N}-1$ for all integers $N$. How would I prove this by using modular arithmetic? I can't remember how to prove this. Any help would be appreciated.
0
votes
0answers
24 views

Finding a primitive root modulo $p$ [duplicate]

Let's attempt to find a primitive root modulo, say, $p=127$. Since $p$ is prime a primitive root exists (more specifically there are $\varphi (\varphi (127))=36$ primitive roots modulo $127$). ...
0
votes
2answers
77 views

If Mr. X was born on April 16, 1987 what day is 2016 days after he was born?

I have a confusion about the way of solving the following mathematical problem: If Mr. X was born on April 16, 1987 what day is 2016 days after he was born? How will I solve these kind of ...
0
votes
0answers
27 views

Understanding Fermats Little Theorem

Say I was told to find: $4^{1000} (mod 7)$ Since The modulo is prime, I can use fermats little theorem, now I'm just wondering if my steps are correct: We have that: $4^6 = 1(mod 7)$ //congruent ...
0
votes
0answers
13 views

conditional in basic arithmetic

So I am creating a CSS Framework (for web), which aim to be very responsive. So here's my problem: Is there a way to get/compute with only using +, -, * and / (basic arithmetic) to replace the if ...
4
votes
1answer
83 views

Find $\sqrt 7 \pmod {2579}$

Find $\sqrt 7 \pmod {2579}$. I think I understand how I would solve a very basic equation like this: $x^2 = 1 \pmod 5$ make a table of all the possible solutions like this $x=0 \implies x^2=0 \\ ...
0
votes
3answers
58 views

Solve the following equation in $\mathbb{Z}_{16}$

I have this equation $\hat{5}x = \hat{6}$ in $\mathbb{Z}_{16}$. I'm not good at all at modular arithemetic. So far I just figured it out that $\hat{5}x = 6+16k, k\in \mathbb{Z}$.
0
votes
0answers
20 views

Modulo composite problem

With $k$ strictly positive integer, we define the sets $A_k\subset\mathbb{N}$ : $$\begin{array}{rl} A_k = \lbrace m& \equiv 5k-1 &\pmod{6k-1}\rbrace\\ \cup \lbrace\lbrace m& \equiv ...
0
votes
1answer
21 views

Modulo pattern with zero skipped

Is there a way to find a modular partern in which 0 doesn't exist. For eg : mod(x,6) 012345012345.... I'd like : 1234512345.... I need it for a rotation in a list but I cant use 0 Thanks !
1
vote
0answers
41 views

More efficient RSA using Chinese Remainder Theorem

Is there a way to increase the efficiency of the RSA algorithm by incorporating elements of the Chinese Remainder Theorem?
1
vote
4answers
80 views

Determine whether $x^2 - 14x + 30 \equiv 0$ mod 1615 is solvable. If so, find its solutions…

Determine whether $x^2 - 14x + 30 \equiv 0\pmod{1615}$ is solvable. If so, find its solutions. I assume the best way to solve this is via Chinese Remainder Theorem, but first i would have to break ...
1
vote
0answers
36 views

Solving $x^2\equiv b \mod p$ for $p$ prime

How do I go about solving $x^2\equiv 116 \mod 587$ for $x$? I know that 587 is prime. How would I get started? I know $116= 2^2\cdot 29$ I think if I can solve $116^{147}\mod 587$, then I will have ...
1
vote
2answers
40 views

If $a \equiv b$ mod n, then $ac \equiv b(c+n)$ mod n

Show that $a\equiv b$ mod n implies that $ac \equiv b(c+n)$ mod n. My proof attempt: If $a \equiv b$ mod n, then $n|(b-a)$ which implies that $(b-a) = nx$ for some $x \in \mathbb{Z}$. Which ...
0
votes
2answers
56 views

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$?

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$? I know that $\gcd(33335+670705093,670726081)$ is a nontrivial factor of $670726081$
1
vote
1answer
38 views

show that $3^{1974} + 5^{1974} \equiv 0 \bmod 13$

show that $3^{1974} + 5^{1974} \equiv 0 \bmod 13$ My attempt with this question was to use Fermate Little's THM. But I do not understand how to properly use it for this question. Can some one show me ...
0
votes
1answer
13 views

$a^2\equiv b^2\pmod n$ and $a\not\equiv \pm b\pmod n\implies\gcd(a+b,n)$ is a factor of $n$?

Suppose $a^2\equiv b^2\pmod n $ and that $a\not\equiv \pm b\pmod n$. How to then show that $\gcd(a+b,n)$ is a (nontrivial) factor of $n$? Hint to get started please.
1
vote
2answers
38 views

Proof of $[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)] \equiv (a+b)\; \text{mod}\; n$

I'm currently self-studying a course in cryptography, and i understand the importance of understanding modular arithmetic fully. I have proved many operations on modular arithmetic, but one i am stuck ...
1
vote
2answers
23 views

Show that if $\gcd(a,pq)=1$ and $g=\gcd (p-1, q-1)$ then $a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$.

Suppose $p\neq q$ are two primes and $g=\gcd (p-1, q-1)$ Show that if $\gcd(a,pq)=1$, then $$a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$$ Hi, how to do? I have no idea how to begin, Thanks.
3
votes
1answer
176 views

Show that $3x^2 - 7y^2 = 1$ has no integer solutions

Show that $3x^2 - 7y^2 = 1$ has no integer solutions A bit confused with this problem, my professor gave me a hint saying that I would need to use a "good mod" although I am not sure how to go about ...
0
votes
1answer
34 views

Let $p$ be and odd prime. Use Wilson's Theorem to show that…

Let $p$ be and odd prime. Use Wilson's Theorem to show that: $[(\frac{p -1}{2}) !]^2$ $\equiv$ $(-1)^{(p+1)/2}$ mod $p$ My understanding is that this should be as simple as picking an odd prime and ...
0
votes
2answers
38 views

Evaluate $2488^{2016}\equiv ?\pmod 7$ [closed]

Evaluate $2488^{2016}\equiv ?\pmod 7$. How do I solve these kind of questions ? Is that modular exponentiation or modular arithmetic ?
0
votes
0answers
23 views

Twin Prime Max Gaps

Ok, let's build a foundation here: A common way of testing primality, is dividing by all primes smaller than the number's square root. For instance, $97$ is prime because dividing by none of the ...
-1
votes
4answers
48 views

Prove that: $2^{n} \equiv 1 \pmod {9} \implies 2^{n} \equiv 1 \pmod {7}$

Prove that: $$2^{n} \equiv 1 \pmod {9} \implies 2^{n} \equiv 1 \pmod {7}$$ Please a hint and a help
0
votes
2answers
36 views

Prove that : $10^{5n+2}+(-1)^{n}\cdot 4 \equiv 0 \pmod {13}$

Prove that : $$10^{5n+2}+(-1)^{n}\cdot 4 \equiv 0 \pmod {13}$$ I don't have enough skills in modular to do it Please help
0
votes
2answers
34 views

Primitive 8th roots of unity in Z17

If $\omega=\frac{\sqrt{2}}{2}+i \frac{\sqrt{2}}{2}$, then $\omega$ is an 8th root of unity. And I know $\omega,\omega^3,\omega^5$,and $\omega^7$ are furthermore primitive 8th roots of unity in ...
2
votes
1answer
77 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
-1
votes
1answer
59 views

Square Root of $5$ mod $10^{9}+7$ [closed]

$My$ $Current$ $Knowledge:$ We can find it if 5 is a $Quadratic$ $residue$ modulo p and where p is prime and we can check it using $Euler$ $criterion$. I cannot able to find the root(5)mod 1000000007. ...
0
votes
0answers
23 views

Modular residue number theory problem.

Given large enough integer $N$ is there always $(\lceil\log N\rceil)^d$ pairs of integers $z,p$ where each of $p$ is distinct prime with $N<p$ and $z$ satisfies $z\bmod p<\frac{zN\bmod p}{N}$ ...
4
votes
1answer
24 views

Defining a homomorphism given a mapping and terminology/notation associated?

So the problem is: "Define a homomorphism $f: (\mathbb{Z}_6, +_6) \ \xrightarrow{onto} (\mathbb{Z}_3, +_3)$. Explicitly tell me how f is defined: Show f is a function, show f is a homomorphism. " ...