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

0
votes
1answer
30 views

How to apply modular arithmatic in expression containing divisions?

How do I find the modulo if the expression contains divisions. Like: $$\frac{p^a-1}{p-1} \pmod{1000,000,007},$$ where $(p^a-1)$ is divisible by $p-1$ and p is a prime, but a may not be. How do I ...
1
vote
2answers
52 views

Problem about proving fermat's little theorem

We know that, there is an important step to prove Fermat's little theorem, two side times $(n- 1)! \cdot a^{n-1} = (a\cdot1)\cdot(a\cdot2)\cdot...\cdot(a\cdot(n-1)) \equiv (n-1)! \mod(n) $ Example: ...
1
vote
4answers
52 views

Problem modulo $p$.

Let $p$ be a odd prime, prove that $1^p+2^p+...+(p-1)^p \equiv 0 \mod p$ I'm not sure how to do this, thanks.
1
vote
1answer
241 views

How to count soldiers in the army using Chinese Remainder Theorem?

You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously. The soldiers can only count from to 1 to 12. ...
0
votes
1answer
43 views

Addition on an Elliptic Curve and Modular Arithmetic involving fractions

I'm having a bit of an issue with addition on elliptic curves. For example, I've been given the curve $Y^2 = X^3 + 2X + 1$, working modulo 3. Now, say I want to add the point $(1,2)$ with itself. To ...
1
vote
1answer
39 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
2
votes
3answers
67 views

Find all solutions to this system of congruences

$$x \equiv 11 \pmod{84} $$ $$ x \equiv 23 \pmod{36}$$ I have the bulk of the work done for this; $x=11+84j$ $x=23+36k$ $\Rightarrow 11+84j \equiv 23 \pmod{36}$ $\Rightarrow 84j \equiv 12 \pmod{36}$ ...
1
vote
2answers
103 views

Find an integer $x$ satisfying the congruence:

$$x \equiv \ 1 \pmod3$$ $$x \equiv \ 2 \pmod5$$ $$x \equiv \ 8 \pmod{11}$$ From the first, I have $x=3k+1$, $x=5j+2$ from the second and $x=11l+8$ from the third. Subbing the third into the second I ...
2
votes
2answers
59 views

Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

$$x\equiv a \pmod {100}$$ $$x\equiv a^2 \pmod {35}$$ $$x\equiv 3a-2 \pmod {49}$$ I'm trying to solve this system of congruences, but I'm only familiar with a method for solving when the mods are ...
2
votes
1answer
58 views

Problem on Number of Quadratic Residues

We have two primes $p,q$ and an integer $a$ such that $$\gcd(a,pq)=1$$ How to prove that for the following congruence $$x^2 \equiv a \mod pq$$ either there will be $4$ solutions or $zero$ solutions. ...
0
votes
3answers
38 views

Computing elliptic curve finite field modular arithmetic

Sorry for asking such a n00b question but what does the following compute to? $s=(3(16)^2+9)\cdot(2\cdot 5)^{-1}\bmod{23} = 11$ In an online response here, I saw this computes to $11$ but whenever I ...
1
vote
1answer
72 views

If $\sigma(p^m)=2^n$ for prime $p$,then $m=1$ and $n$ is prime

Exercise from Beginning Number Theory by Neville Robbins: Let $\sigma(a)$ denote the sum of divisors of $a$.Then we have to prove that if $\sigma(p^m)=2^n$ for some prime $p$,then $m=1$ and $n$ is ...
-1
votes
2answers
36 views

How to prove this modular problem?

Prove that if $n^2+m$ and $n^2-m$ are perfect squares, them $m$ is divisible by $24.$ How to solving this problem?
0
votes
2answers
58 views

Extended Euclidean Algorithm for Modular Inverse

I'm currently learning how to find the inverse of a modulo with the Extended Euclid Algorithm and I stumbled upon a problem when finding an inverse when the $m>p$ as for $m \equiv 1 \pmod{p}$ For ...
0
votes
2answers
40 views

How to prove that gcd(k! mod m, m) > 1, for every k > $\alpha$

I'm doing some exercises and I've read that, if $\alpha$ is the first prime factor of a number $m \geq 2$, then, for every $k \geq \alpha$, it is true that $gcd(k!\ mod\ m,\ m) > 1$. I can see ...
0
votes
4answers
39 views

Are $a$ and $n$ relatively prime?

Suppose that $a$ and $n$ are integers, $n>1$. Prove that the equation $ax\equiv1(\mod n)$ has a solution if and only if $a$ and $n$ are relatively prime. How to solving this problem?
0
votes
5answers
62 views

Prove that $p^q+q^p\equiv p+q \mod pq$

I can prove $p^{q-1}+q^{p-1}$ is congruent to 1 mod $pq$ very easily, but with the $p+q$ it doesn't fit a theorem I can find. The only ones I find say if they are congruent to $b$. I get one is ...
0
votes
1answer
59 views

Is there this integers [duplicate]

Given an integer n, show that an integer can always be found which contains only the digits 0 and 1 (in the base 10 notation) and which is divisible by n. How to solving this problem?
1
vote
1answer
37 views

Prove that there exists an integer n

Let a,b,c,d be fixed integers with d not divisible by $5$. Assume that m is an integer for which $am^3+bm^2+cm+d$ is divisible by $5$. Prove that there exists an integer $n$ for which ...
0
votes
2answers
71 views

How does one compute how big the cycle of modding by a prime number is?

If I take the $k \in \mathbb{N}$ power of 10 and mod it by a large prime, I notice that the remainders repeat at some point. For instance $10^k mod~7$ seems to repeat every $8$th value of $k$. Given ...
2
votes
5answers
146 views

Prove they cannot both be integers

Prove that $\frac{21n-3}{4}$ and $\frac{15n+2}{4}$ cannot both be integers for the same positive integer $n$. How to solving this problem?
5
votes
6answers
439 views

Show that if n divides a single Fibonacci number., then it will divide infinitely many Fibonacci numbers. [duplicate]

Show that if n divides a single Fibonacci number, then it will divide infinitely many Fibonacci numbers.
0
votes
1answer
53 views

Remainder of $1946^{1972} : 26$

Is this correct? $1946^1 = 22 \mod{26}$ $1946^2 = 22^2 = 484 = 16\mod{26}$ $1946^3 = 22^2 * 22 = 16 * 22 = 14 \mod{26}$ $1946^4 = 22^2 * 22^2 = 16^2 = 22 \mod{26}$ And therefore for any integer ...
0
votes
1answer
22 views

How to decide whether a number is inside of wrapped (modular) interval

I am having a problem a finding a suitable formula for deciding whether a number falls inside of modular interval. Example: Let's use $mod$ $100$ and the interval $\langle 90, 10\rangle$. How would ...
1
vote
4answers
54 views

How to find $k$ in $6^{k} \equiv 2 \mod {13}$

Find for which $k$ is $6^{k} \equiv 2 \mod {13}$ I'm having trouble with these types of question in my cryptography class. This is part of Diffie–Hellman algorithm for calculating a shared key. ...
1
vote
3answers
368 views

Determine the last two digits of $3^{3^{100}}$

Determine the last two digits of $3^{3^{100}}$ This is one of the problems in the past exam my modern algebra course. I think I need to use euler-fermat theorem but can't figure out how to use it for ...
0
votes
2answers
56 views

Congruence and GCD relation proof

I came across this theorem: For all integers a,b,c and m>0, if d = GCD(c,m) then ...
0
votes
4answers
45 views

Inverse $2^{18}$ in GF(23) without extended euclidean algorithm

I have a little question about the calculation of the inverse of $2^{18} \mod\ 23$. I have the solution of this: $$ \text{The inverse of $2^{18}$ is $2^{-18}$. The modulus in the exponent is ...
0
votes
1answer
37 views

Explanation and validation of point adding/doubling on elliptic curves

I'd like to implement point multiplication on elliptic curves over prime fields. My problem is that I've found different definition how to do it. At adding: the second parameter of the result is not ...
1
vote
2answers
92 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
0
votes
1answer
369 views

Solving mod congruence

So i have a problem like this 34x ≡ 77 (mod 89) This is how i try to solve it but it doesn't seem to work :( If anyone can give me a hint on how to proceed from ...
0
votes
3answers
72 views

Discrete mathematics. Just an impression, or this is always true?

I feel that the following is always true: $$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \text{ if }k \equiv 0 ~(\text{mod }2) \wedge k \geq 2$$ I've just tried it using a "brute force" approach, but ...
2
votes
1answer
31 views

modulo of 2 polynoms

I'm trying to understand the example given in the wikipedia explanation of the algorithm of Reed Solomon: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction. We have $p(x) = 3x^6 + ...
2
votes
4answers
231 views

Proving congruence modulo, number theory

The task is to prove $24^{31}\equiv 23^{32}\pmod {19}$. I'm trying to use Fermat's little Theorem and so far I only found that $24^{31}\equiv 19\pmod{19}$. Would proving that $17\mid23^{32}$ prove ...
0
votes
2answers
71 views

Solving modular arithmetic equation.

Need help! I'm having some problem with understanding this equation! We have a similiar example in the book, but I dont really get what they mean. So here is the question. Given 3u = 1 (mod 5), find ...
1
vote
1answer
30 views

Question about multiplication of modulars

Why is the property when you multiply two modulars (you multiply the two ones on outside and the two ones inside) Why does that property hold true? Addition is easy but multiplication doesn't make ...
0
votes
1answer
39 views

Congruence and modular arithmetic

$228,547,866$ divided by $q$ leaves the remainder of $r$. Find $r+q$. The problem is designated to be solved by using modular arithmetic. Even though I haven't learned what that is.
0
votes
1answer
54 views

GCD of polynomials

In $\mathbb{Z}/5\mathbb{Z}[x]$ use the Euclidean Algorithm to find the GCD of $x^4+x^2$ and $x^4+x^3+3x$. My thoughts: I am getting to the point where I need to use a fraction to get further in ...
0
votes
2answers
97 views

Finding unknown in modulo operation

I have this question on a test 1) find d=gcd(77,50) using euclidean alg. 2)find s and t such that 77s+50t=d 3) use these results to find x such that 50x=4(mod77) Note:the qual sign should have 3 ...
0
votes
1answer
52 views

Rules on surjective and Injective

So I am trying to prove $f([a]+[b]) = f([a]) + f([b])$ for $\mathbb Z$ mod $12$ and the same for multiplication... Can you show that this is true based on a function being surjection and injective ...
1
vote
1answer
51 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...
0
votes
1answer
37 views

Getting higher powers in modular arithmetic

How would I solve $7^{\ 345}+4^{2313} \equiv x \pmod 3$ ?
1
vote
3answers
636 views

Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017). So, this is what I have; By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 ...
4
votes
2answers
75 views

Generalization of $n$ mod $2 = \dfrac{1-(-1)^n}{2}$

I had this idea that $n$ mod $2 = \dfrac{1-(-1)^n}{2}$ for $n \in \mathbb{N}$. Are there any generalizations for this? For example for $n$ mod $3$ etc.? I would prefer some answers containing basic ...
3
votes
3answers
170 views

Prove that the equation $x^3 + 10000 = y^3$ has no solutions

The below question was given in my workbook for number theory. I have seen the solution, and it utilizes $\mod 7$, but I am unsure of why $\mod 7$ was chosen to solve the problem. Would any number of ...
1
vote
1answer
35 views

modular arithmetic problem (when solving elliptic curves)

Given E: (elliptical curve) $y^2 = x_3+2x+2 \bmod 17$ Recall: $y^2 = x^3+ax+b$ point $P=(5,1)$ Compute: $2P = P+P = (5,1)+(5,1)= (x_3,y_3)$ Now the formula used here is slope $m = \dfrac{3x_1^2 ...
10
votes
2answers
297 views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod n, where $n=pq$ is composite, as I understand we have ...
1
vote
3answers
195 views

Find a number congruent to mod

Can anyone give a hint of how to go about solving this? Please don't give answer thanks Find the integer a such that ...
1
vote
1answer
66 views

Negative quotients and their remainders

Since $16 \div{-3} = -5.\overline{3}$, I thought I could also express this as $16 \div{-3} = -5\:R\:1$ or in other words $16\mod{-3} = 1$. My calculator tells my it is in fact $-2$. Along the same ...
1
vote
2answers
210 views

Multiplication of residue classes modulo n

If $\bar{a}$ and $\bar{b}$ are residue classes modulo $n$, it is straightforward to see that $\bar{a} \bar{b} = \overline{ab}$. But given that those classes are sets, does the $=$ mean set equality? ...