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

1
vote
1answer
32 views

Conjecture concerning modular arithmetic

Below $0\notin\mathbb N$. I want a proof or a counter-example of the following (corrected) conjecture: Suppose $p$ is the smallest prime dividing $n\in\mathbb N$ and suppose $kn+ap=m!$, where $...
0
votes
0answers
10 views

Solving for exponent in modular arithmetic equation

Let there be two numbers $a$ and $d$ such that GCD(a,d) = 1. For a given value of $k$, how many solutions are there for: $$d^xk = k \mod a$$ We know that if GCD(a,k) = 1, then there is only one ...
0
votes
0answers
7 views

How to keep result of calculation to be in particular range?

I have data as :- Group A Element A score(3) Element B score(1) score 4/2 ...
2
votes
1answer
99 views

Conjecture about primes and the factorial

Conjecture: Given a prime $p>5$ there exist a prime $q<p$ and $k,m\in\mathbb Z_+$ such that $kp+q=m!$. I want help to prove the conjecture or to find a counter-example. I've changed from $...
1
vote
0answers
46 views

No square has a decimal expansion ending in 79

Show that no square number has a decimal ending in 79. More generally, find all possible two-digit endings for squares. Let any digit number ending at 79 be represented as $$a_nx^n+.....+7x+9$$ Plug ...
0
votes
2answers
34 views

How to apply Chinese Reminder Theorem to this congruence system?

\begin{align*} 17x & \equiv -15 \pmod{5}\\ -11x & \equiv 5 \pmod{3}\\ 23x & \equiv 15 \pmod{7} \end{align*} $5$, $3$, $7$ are coprime, so the system has solution mod $105$. I'm not sure ...
2
votes
0answers
32 views

Proof of the Ribet's theorem

My question is very simple : My goal is to read a proof the proof of the epsilon conjecture proven by Ken Ribet (1986) which is an ingredient of the proof of the Fermat Last Theorem (I want the ...
1
vote
1answer
26 views

Remainder modulo matrices.

Is it possible to have a consistent definition of $A\bmod_{left} B$ that respects matrix multiplication from left where $A$ and $B$ are two square matrices with non-negative entries? Is there a ...
1
vote
0answers
11 views

What are good parameters for an $ax+b \pmod{2^L}$ hash with distinct first n bits of the first $2^n$ inputs?

I'm hashing 64 bit integers via $ax+b \pmod{2^{64}}$. Good parameters mean that, given an $1 \leq n \leq 64$, the first $n$ bits of the first $2^n$ inputs are distinct. How should I chose $a$ and $b$ ...
0
votes
1answer
31 views

Calculating the last digit of exponent

I need to calculate the last digit of $723^n$.(For every positive integer $n$). If it was to calculate the last digit of $a^b$ when I know the value of $a$ and $b$,then it was easy- for example,If I ...
0
votes
4answers
85 views

Why k should be odd? [duplicate]

My teacher once said, for any positive number $\ n, $ $\ n^k - 1 $ would always have $\ n-1 $ as a factor for all positive odd values of $\ k $. Could anyone tell me the proof? I have written my ...
2
votes
0answers
50 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
4
votes
1answer
73 views

Pattern in numbers

I bumped into this mathematical calculation while driving my car. With lot of traffic jams and lot of time to kill, I did some scrambling of the registration numbers of the cars in front of me. I ...
0
votes
4answers
72 views

How to approximate

I was reading a book and saw this approximation $(1 - 10^{-3})^{1023} \approx 2^{-1.476}$ I am wondering how it is calculated.
1
vote
1answer
28 views

How many more legs than seats are in the leftover inventory (use modular-arithmetic)?

I have difficult with this problem, and appreciate any help. The Seats R Us factory produces chairs with four legs and stools with three legs. The seats and legs are the same for both chairs and ...
2
votes
2answers
36 views

Find two integers between 1 and 100

Can anyone help me with this? Thank you very much! Problem: Find two integers between 1 and 100 such that for each: a) if you divide by 4, the remainder is 3; b) if you divide by 3, the remainder ...
1
vote
1answer
33 views

What is the value of $N$ in a three-digit number $1N1$?

I don't know how to solve this problem. This is as far as I can go. $$\frac{1N1}{N}=2N+5$$ Then what should I do from there? Any help is highly appreciated. If a three-digit number of the form $...
-1
votes
2answers
36 views

Given $(c -x) % (n - 1) == 0$ for some $x$, how do I find a suitable $x$?

Given $(c - x)$ $mod$ $(n - 1)$ $= 0$ for some $x$, how do I find a suitable $x$? $c$ = constant $x \ge 2$ $n - 1$ = constant
2
votes
4answers
103 views

Is this possible to solve through algebra?

$$150 \equiv 17 \mod x, \qquad 100 \equiv 5 \mod x $$ Solve the simultaneous equation? Is this even a simultaneous equation? How do I find the value of $x$ too? I was doing a question and came up ...
0
votes
1answer
32 views

Solving algebraic equations with modulus [closed]

How do I solve for 'b' given: $1 \equiv a\pmod{2} \\ a=\frac{b-1}{3}$
1
vote
1answer
35 views

Is there an integer z such that $255z\equiv 7\pmod {633}$?

I used the extended euclidean algorithm to "Find integers x and y such that $633x + 255y = 6$, or explain why none exist." And found that $6x = -58$ and $y = 144$. Now I'm stuck on the follow up ...
1
vote
0answers
42 views

Use modular-arithmetic to solve a scheduling problem

Can anyone help me with this? I know the problem is related to mod, but I don't know how to solve it using modular-arithmetic. Three professors start to teach math on the first Monday, Tuesday, ...
0
votes
1answer
53 views

Alternate way of showing infinitude of primes of the form $4m+1$

I would like to know if my approach is valid. I want to show that there are infinitely many primes of the form $4m+1$. Assume the contrary, and denote each of these primes by $p_{i}$ with $i \in \{1,...
0
votes
2answers
20 views

Number of solutions for $a$ of $x^2\equiv a \pmod3$

Find the all the numbers $a$ such that for $x^2\equiv a \pmod3$ there is: A. exactly one solution. B. two solutions. C. three solutions. D. no solutions. My attempt: $$1^2\...
1
vote
2answers
58 views

Find the last digit of $66^5$

Find the last digit of $66^5$. This is how I solved the problem: $66^5=6^5*11^5$ (mod 10) = $6^5*1^5$ (mod 10). I have two questions. First, what is wrong with my method? I get different answer from ...
2
votes
4answers
63 views

Solve $x^2+x+1\equiv0\pmod5$

Solve: $$x^2+x+1\equiv0\pmod5$$ My attempt: Our proffesor told us that if we have $ax^2+bx+c\equiv\pmod p$ we need to multiply by $4a$, to get form of $(\text{ something})^2\equiv D\pmod p$. $...
2
votes
4answers
92 views

how to solve $x^{113}\equiv 2 \pmod{143}$

I need to solve $x^{113} \equiv 2 \pmod{143}$ $$143 = 13 \times 11$$ I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$ By Fermat I got 1) $x^{5} \equiv 2 \pmod{...
2
votes
4answers
69 views

Find smallest $x$ such that $x=59 \pmod {60}$ and $x=1 \pmod 7$

Is a simple way to solve the problem? The method I used is to list all numbers from equation (1) and then see which one give remainder $1$ when divided by $7$. This doesn't seems a very smart way. ...
0
votes
0answers
45 views

How to solve a modular inequality with optimization?

I have this: $x\le y$ $ y\lt m$ $x^2\mod m < y$ $y$ and $m$ are given. I am trying to maximize the value of $x$. Any advice on how to approach this?
1
vote
1answer
255 views

Remainder when dividing $13^{3530}$ with $12348$ [duplicate]

Find the remainder when dividing $13^{3530}$ with $12348$. How do I solve these type of exercises? I know there's some algorithm for solving them, I just haven't found a concrete example. Could ...
17
votes
0answers
230 views
+50

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
0
votes
2answers
46 views

Which of the following will give a remainder of 1?

Which of the following will give a remainder of $1$ ? $1$. $2^{100}$ divided by $7$ $2$. $2^{110}$ divided by $11$ $3$. $3^{140}$ divided by $11$ $4$. $12^{112}$ divided by $113$ Could someone ...
2
votes
13answers
123 views

Prove that for all odd integer $n, n^{4}=1\pmod {16}$

My answer: $n=2k+1$ $n^{4}=(2k+1)^{4}$=$16k^{4}+32k^{3}+8k^{2}+24k+1$. I do not know how to conclude; really needed help here.
3
votes
1answer
114 views

Can it be proven using congruence?

We now that $a^3 +b^3=c^3$ has no solution if $a,b,c\in\mathbb{N}$(thus non of $a$, $b$ or $c$ can be zero). Well I want to know whether this can be proven using congruency(Like how we can prove that ...
6
votes
1answer
61 views

Does $n^n\mod p$ repeat every $2p$ terms?

Going through some random numbers, I have found that $n^n\mod10$ repeats every $20$ terms, and it more or less is as follows. $$1^1\equiv1\pmod{10}$$ $$2^2\equiv4\pmod{10}$$ and so on. The ...
1
vote
1answer
14 views

Why is that any positive integer a such that gcd(a,p) = 1 for p = 31 has order n modulo p where n|p-1?

Any hints? Fermat's little theorem is crucial, I think; however, I can't seem to quite wrap my head around it.
1
vote
2answers
32 views

Known rules for multiplication of modulo operator

Say for example I have the formula: y = x%2 * x%3 or to put it in word notation: y = mod(x,2) * mod(x,3) Is there any way ...
1
vote
1answer
24 views

A question on divisibility of binomial coefficient

In this paper, page 3, theorem 4, the author claimed that If $m, n, k$ are three positive integer such that $\text{gcd}(n, k)=1$ then $\binom{mn}{k}\equiv 0\pmod n$. And he proved it as ...
2
votes
1answer
40 views

Finite groups and prime divisors. Understanding how to deduce a claim from a certain proof.

In my algebra textbook, it goes like this. First, there is presented Cauchy's theorem: Let $G$ be a finite group, and let $p$ be a prime divisor of $|G|$. Then $G$ contains an element of order $p$....
1
vote
1answer
30 views

find how many quarters a person has using modular arithmetic

How to solve this problem using modular arithmetic? Wendy noticed when she stacked her quarters in piles of $5$ she had $3$ left over, and when she stacked them in piles of $7$ she had $5$ left ...
0
votes
1answer
25 views

Solving simple diophantine equation with modulos

I need to solve this diophantine equation using a positive integer $x$: $$x^2 + 42x + 21 \equiv 0 \mod 105$$ I think it will be easier if I could use the prime factors of $105$ to get a system of ...
-1
votes
0answers
54 views

A square-related question in modular arithmetic…

Let $n$ and $k<\frac{n}{2}$ be integers with $4|n$. Find the pairs $(n,k)$, such that: $i(k-1)\not\equiv\frac{n}{2}\pmod n$, for all $i\in\mathbb{Z}_n$, or $i(k+1)\not\equiv\frac{n}{2}\pmod n$, ...
1
vote
2answers
46 views

Equation involving the Jacobi symbol: $\left( \frac {-6} p \right) = 1$?

I have to determine the values of $p \in \{0, \dots, 23 \}$ such that $\left( \frac {-6} p \right) = 1$. I have that: $$\left( \frac {-6} p \right) = \left( \frac 2 p \right) \left( \frac {-3} p \...
0
votes
1answer
21 views

modular alzebra

Like alzebra can I write the following? 1.(a+b+c+d+. . .n) % m = (a%m) + (b%m) + . . . +(n%m). 2.(abcd. . .n) % m = (a%m) * (b%m) * . . . *(n%m).
0
votes
1answer
42 views

Basic question with coprimes and modulos

I started reading about Modular Arithmetic and solving some random basic exercises, and this one appeared: "Find an integer number $a$ such that any $b$ coprime with 34 is congruent to $a^k \mod34$ ...
1
vote
2answers
83 views

Is this the correct way to compute the last $n$ digits of Graham's number?

For the following question, all what is needed to know about Graham's number is that it is a power tower with many many many $3's$ Consider the following pseudocode : input n Start with $s=1$ and $...
0
votes
4answers
58 views

Solve a set of modular equations

Can someone give a hint to me about this problem? :/ This is so hard for me: Find the total number of solutions to the following system of equations: $a^2+bc \equiv a \pmod{37}$ $ba+bd \equiv b \pmod{...
4
votes
2answers
86 views

Binomial coefficients mod p

I want to find the following sum mod $p$ (prime number): Let $i\geq \frac{p-1}{2}$, $ \sum_{k=i}^{p-1} \binom{k}{i}\binom{k}{p-i-1} \pmod{p} $ OK, I succeeded in simplyfying this argument to the ...
2
votes
3answers
86 views

Find the remainder when $11^{12}$ is divided by $13$. [duplicate]

I am looking for an easier way than mine to solve the problem. Problem: Find the remainder when $11^{12}$ is divided by $13$. Here is what I did. I simplify $11^{12}$ mod $13$ = $(–2)^{12}$ mod ...