4
votes
2answers
90 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
-1
votes
0answers
8 views

How can I solve a mod system of equations for this hill cipher? [duplicate]

I am having trouble eliminating these variables when I try to solve this system of equations. They may not even be the right equations, but it would be nice to see this worked out so I can try my next ...
0
votes
1answer
44 views

Proof that $ax \equiv 1 \mod{n}$ has no solutions when $a$ and $n$ aren't co-prime?

Does this proof work? Is there a simpler one (precluding citing other theorems)? Suppose $ax \equiv 1 \bmod{n}$. Then $ax = kn + 1$. We have some $d = \gcd(a, n)$ such that $a = da'$, $n = dn'$, and ...
0
votes
0answers
31 views

Solving system of equations using mod math for a Hill cipher

I am having trouble eliminating these variables when I try to solve this system of equations. They may not even be the right equations, but it would be nice to see this worked out so I can try my next ...
1
vote
0answers
52 views

[ANSWERED]Is $\{n, n^{2} n^{3}\}$ a group under multiplication modulo $m = n + n^{2} + n^{3}$?

My number theory has been lacking, so i decided to practice it a bit. I have gotten better in the sense that i can figure out where to begin approaching a problem, but i am having trouble seeing the ...
0
votes
3answers
44 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
0
votes
1answer
44 views

Exist an explicit formula to calculate the minimum number of divisions by two that leave a rest < 0.5?

I have a number $x \in \Bbb R/\Bbb Z$ (i.e. any number but entires) and I want to know if exist a explicit formula that evade recursion to calculate the minimum n that $$\frac{x}{2^n}\mod ...
1
vote
1answer
46 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
0
votes
1answer
19 views

On the Product of Congruence Classes over $\mathbb{Z}$

Is it possible to multiply an element $a$ of $\mathbb{Z}_4$ to an element $b$ of $\mathbb{Z}_2$? If so, what are the needed conditions? To which set ($\mathbb{Z}_4$ and $\mathbb{Z}_2$) does $a\cdot b$ ...
2
votes
0answers
34 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
0
votes
2answers
79 views

how can i find modulus of the sum of first n natural numbers raised to power 4? [closed]

suppose i am given with a number p and a number n then i want to calculate : (1^4 + 2^4 + 3^4 + 5^4 +........n^4)%p earlier i was trying to use the standard formulae of sum of first n natural ...
2
votes
0answers
47 views

Closed form for the sum $\sum_{a=1}^{b} a^3\cdot (b \bmod a)$

How can we simplify $\sum_{a=1}^{b} a^3\cdot (b \mod a)$? For $a \ge \frac{b+1}{2} $ to $a = b$ it reduces to $$\sum_{a\ge \frac{b+1}{2}}^{b}a^3\cdot (b-a)=b\cdot\sum_{a\ge ...
-2
votes
2answers
139 views

How to find sum of 4th power of n numbers mod m [closed]

How can i calculate $1^{4} + 2^{4} + 3^{4} + 4^{4} .....+n^{4} \pmod m$ where $1 \le m \le 10^5$ and $1\le n \le 10^{20}$. I can't use the formula here because it will Overflow the limit of long long ...
1
vote
1answer
27 views

If f(n) is congruent to r(mod m), is f(km + n) congruent to r(mod m)?

I am currently working on a number theory book and I came across a question about the divisibility of two consecutive cubes. While solving it, I realized that my solution relied on the following to be ...
3
votes
2answers
83 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
0
votes
3answers
60 views

modules with several powers $x^{y^z}$

I have an assignment(which gives no credit) which I cant solve so I would like to get some help $3^{{1001}^{1002}}\pmod {43}$ (All original numbers were replaced) Our hint was to use the ...
2
votes
3answers
149 views

remainder when 67896789…(300 digits) divided by 999

What is the remainder when 678967896789... (300 digits)is divided by 999? i tried to divide it manually to find some pattern in remainder. But was getting bit lengthy. so please suggest me some short ...
3
votes
1answer
83 views

Remainder on dividing $10^{n} + 10^{n-1} + … + 10^{1} + 10^{0}$ by x

Given a positive integer $n$, consider the number $y=10^{n}+10^{n-1}+$$...+ 10^{1}+10^{0}$. I need to find the remainder when $y$ is divided by a natural number $x$. e.g. $111111$ $\%$ $2123$ = ...
0
votes
1answer
47 views

Under what conditions can we obtain $a \equiv 1 \pmod{mn}$ from $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$?

If $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$, are there any conditions under which we can conclude that $a \equiv 1 \pmod{mn}$? Here $m$ and $n$ are any integers; $a$ and $b$ are both coprime ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
2answers
106 views

Modulus of large powers

Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$. We need to find if $X \mid ...
0
votes
2answers
80 views

Find all non-trivial triplets $(a,b,c)$ such that $ a+b^{d}\equiv0\pmod c $ for all $d>0$

Let $a,b,c$ be co-prime integers $>2$ . Find all non-trivial triplets $(a,b,c)$ such that $ a+b^{d}\equiv0\pmod c $ for all $d>0$.
4
votes
0answers
192 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
0
votes
1answer
32 views

What is the smallest number of times that the digit 1 can appear in N?

All the digits of the positive number $N$ are either $0$ or $1$. The remainder after dividing $N$ by $37$ is $18$. What is the smallest number of times that the digit $1$ can appear in $N$? I have ...
4
votes
2answers
115 views

Sum of two squares modulo p

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How ...
1
vote
1answer
41 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
1
vote
4answers
159 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
2
votes
0answers
95 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
46
votes
4answers
3k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
1
vote
3answers
69 views

Additive identity in $\mathbb{Z}_{7}$

The problem consists of two parts: 1)Prove that for some integer $m,$ $3^{m} = 1$ in the integers modulo 7, $\mathbb{Z}_{7}$, which i have done. The second part asks to use this fact to deduce that ...
0
votes
1answer
195 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
0
votes
1answer
38 views

Reverse Modulus Operator with given condition

I have an equation: $$ x^2 \mod p = z $$ $p$ and $z$ are given. $x$, $p$ and $z$ are positive integers and a maximal value of $x$ is given (say $M$). $p$ is a prime. How can i calculate (multiple ...
1
vote
0answers
14 views

Jacobi Form and its Fourier expansion

Let k,m be non negative integers. A Jacobi form of weight k and index m is a holomorphic function f on $\mathbb{H} x \mathbb{C}$ (where $\mathbb{H}$ denotes the upper half plane) satisfying the ...
1
vote
3answers
36 views

What are the members of the set $A=7^{n}+5^{n}(mod35)$

I have this set $A=${$\ x \ \in \mathbb{N}|\ \exists \ n \ \in \mathbb{N}:$ $x \equiv 7^{n}+5^{n}$ (mod $35$) $ $, $ 35\gt x\ge 0$} I want to know how many members has this set? thanks in advance
0
votes
2answers
36 views

How to prove that $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$)

I'd like to solve this problem but I can't $\exists \ m,n \ \in \mathbb{Z}$ & $ m\gt n\ge 0$ $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$) Any ideas? Thanks in advance.
0
votes
1answer
42 views

Polynomial Diophantine Equations

So in general how does one decide if: $$ a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers $x,y$ given real numbers $a_0, a_1. .. a_{n_1}, b_1 , ...
1
vote
2answers
81 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
0
votes
1answer
33 views

Proof that the repeating block of digits in 1/x is at max x-1?

The question is self-explanatory, I suppose. Example, the maximum number of digits in the repeating block of 1/17 is 16. Thanks in advance.
2
votes
1answer
45 views

The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3 $$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...
1
vote
1answer
37 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
0
votes
1answer
117 views

What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
2
votes
2answers
32 views

Why is $a^{n/2} \equiv -1 \mod p$ but not necessarily -1 modulo a composite?

I'm going over a review sheet in preparation for my number theory final. We are asked to prove the following: |a| = 2r, show that $a^r \equiv -1\mod p$ a prime. Does this hold modulo n, where n is a ...
0
votes
1answer
36 views

Simple modulo congruence operation

Find a number $n$, with $0 \leq n < 15$, so that $6 \times 7$ is congruent to $n$ modulo $15$ Please explain your work.
1
vote
3answers
63 views

Calculating $x^{103} \equiv 2 \pmod{143}$

I need to find x, given that: $0\leq x \leq 143$ and $x^{103}\equiv 2 \pmod{143}$. I tried to use Euler's theorem $p(143)=120$, but it didn't help.
2
votes
0answers
23 views

System of equations - modular arithmetic

I am asked to solve the following..... Let $n\in \mathbb{N}$ and suppose that $a,b,c,d,k,l\in\mathbb{Z}$. Consider the system $ax + by \equiv k$ mod $n$ and $cx+dy \equiv l$ mod $n$. Let $D=ad-bc$. ...
0
votes
1answer
45 views

question about the forms of prime numbers

I was thinking about primes earlier and I thought of a hypothesis that I have been unable to prove. I was wondering whether it was a known theorem and whether anyone knows a proof or can prove (or ...
-3
votes
3answers
183 views

Congruence $x^n\equiv2 \pmod{13}$ (Multiple Choice)

I was trying to solve the following problem.Please help. Consider the $x^n\equiv2 \pmod{13}$. It has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ It may have more than one correct options. Thnx ...
3
votes
3answers
62 views

Solve for x in $5 \equiv 128x$ (mod 59)

I'm just running a blank here in review for finals and cannot seem to figure it out for the life of me. I want to say that you must use extended euclidean algorithm somehow, and I checked that the ...
0
votes
3answers
35 views

Modular equations, find x

Problem: Find an integer $x$ such that $x = 5\pmod 8, x = 3 \pmod 9, x = 4 \pmod 7$. Attempt: By the Chinese Remainder Theorem " Suppose $a_1,a_2,...a_k$ are integers pairwise relatively prime ...
0
votes
1answer
43 views

For every positive integers $a$ and $n$, is it true that: $a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$?

Based on Fermat's little theorem or on Euler's theorem, is the statement $$a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$$ true for every positive integers $a$ and $n$?