Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

2
votes
1answer
79 views

Intervals of Circle Method

I'm trying to understand how to use the circle method to derive an asymptotic formula for Waring's Problem. Do so using the circle method developed by Hardy and Littlewood. In doing this, I want to ...
3
votes
1answer
69 views

$ x_1 + x_2 + x_3 +\cdots + x_m = k $

What I'm tyring to show is the number of solutions to the equation of natural numbers; $$ x_1 + x_2 + x_3 +\cdots + x_m = k $$ is equal to $$ \binom{m + k - 1} m $$ To be blunt, I have no idea ...
2
votes
1answer
109 views

Show that if $p\ge5$ then $(mp)! \equiv m!p!^{m} \pmod{p^{m+3}}$.

This is a question in Niven's An Introduction to the Theory of Numbers. I believe a result from the previous exercise If $p\geq 5$ and $m$ is a positive integer then $\binom{mp-1}{p-1} \equiv 1 ...
2
votes
2answers
69 views

For what values of the variable x does the following inequality hold:

$\ \frac{4x^2}{\Bigl(1-\sqrt{\ 1\ +2x}\Bigr)^2} < 2x+9$ ... IMO-1960
1
vote
2answers
302 views

Addition or subtraction in GCD and LCM

Suppose that we have two integers $a$ and $b$. Now say that $G = \gcd(a,b)$ and $L = \mathrm{lcm}(a,b)$. Now the value of $G$ and $L$ is given and another integer $c$'s value is given. How can we find ...
4
votes
4answers
167 views

How to eliminate these extra solutions? (finding the gcd of two expressions)

Prove that for any integer $n$, $\gcd (3n^2+5n+7, n^2+1)=1$ or $41$. The following answer is convoluted because I've intentionally created excess solutions. However, I can't figure out how to ...
1
vote
1answer
215 views

Possible primes $p$ $q$ satisfying $a^{3pq}-a \equiv 0 \pmod {3pq}$

For any integer $a$, consider the primes $p$ and $q$ satisfying $a^{3pq}-a \equiv 0 \pmod {3pq}$ Find all such possible $p$ and $q$. So I tried breaking it down into 3 congruences: $a^{3pq}-a ...
0
votes
1answer
71 views

Find the lowest number that's $\geq N$ and that multiplying it with a set of numbers results in natural numbers

Given a set of numbers, I need to find the lowest number that multiplying it with each of the numbers in the set results in a natural number, while being bigger or equal to $N$. For example, for the ...
1
vote
0answers
139 views

Find the lowest common divisor greater than N?

For a given set of numbers, I need to find the lowest common divisor that's higher than a given number, N. Is there a way to do that?
1
vote
0answers
51 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
0
votes
2answers
161 views

Find the congruence of $4^{578} \pmod 7$

Find the congruence of $4^{578} \pmod 7$. Can anyone calculate the congruence without using computer? Thank you!
0
votes
1answer
336 views

Determining the existence of an integral linear combination

Given $x, y, r \in \mathbb{Z}$, how can you tell whether there exist two integers $a$ and $b$ such that $ax + by = r$? That is, how do you determine whether an integral linear combination exists for ...
1
vote
2answers
154 views

Roots of unity in $\mathbb{C}$ sum of roots

I want to know why if $F(n)$ denote the sum of the primitive $n$th roots of unity in $\mathbb{C}$, and $G(n)$ denote the sum of all complex $n$th roots of unity. Then $G(n)=\sum_{m|n}F(m)$, Please, I ...
1
vote
1answer
120 views

What about the Cauchy-Frobenius-orbit-counting formula

I know the proposition that says: Let $\lambda$ be a homomorphism from a finite group $G$ into $\mathbb{C}^{\times}$. Suppose that $G$ acts on some finite set $\Omega$ and let $M$ be the number of ...
6
votes
1answer
242 views

Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function.

I need to prove the proposition. Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$
5
votes
2answers
330 views

Roots of unity and function $\mu$

I need to prove that for each positive integer $n$ the sum of the primitive $n$th roots of unity in $\mathbb{C}$ is $\mu(n)$, where $\mu$ is the Möbius function.
4
votes
3answers
165 views

A question about Fermat numbers

This is a question in a book in Portuguese. Let $p_n$ be the $n$-th prime number. Show that $p_n\leq 2^{2^{n-2}}+1$. The book gives a hint: use the facts that $\gcd(F_i,F_j)=1$, if $i\neq j$, ...
4
votes
3answers
168 views

Find the number of integral solutions of $(x,y)$

Given this equation: $4x^3+5=y^2$ Find the ordered pairs of $(x,y)$ where $x,y\in Z$
0
votes
2answers
105 views

Sylvester Theorem

Bonjour, The equation $\binom{n}{k}=m^l$ has no entire solution for l$\ge$2 and 4$\le$k$\le$n-4. Suppose that n$\ge$2k (since $\binom{n}{k}=\binom{n}{n-k}$). According to the Sylvester theorem, the ...
3
votes
1answer
113 views

$x^2 \equiv 2x \pmod m$

Toward counting the solutions for the congruence $x^2 \equiv 2x \pmod n$, if we write $m$ as $m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}$ we have the following equivalent system of congruence equations: ...
2
votes
0answers
135 views

For which positive integers n does there exist a prime whose digits sum to n?

Motivated by this earlier question, I thought of this problem: Question: For which positive integers $n$ does there exist a prime whose decimal digits sum to $n$? We can make two "easy" ...
1
vote
0answers
61 views

Proof of a Continued Fraction Identity using basic CF definition.

Two definitions (the first is informal) of continued fraction: This is the basic Continued Fraction algorithm for real numbers. Let $\alpha \in \mathbb{R}$. If $[\alpha]=\alpha$, then we are done. ...
1
vote
3answers
190 views

Number Theory Problem $ax+by=n$ for $n>ab$

Let $a,b \in \Bbb N$ with $\gcd(a,b)=1$. Show that for every integer $n>ab$ the equation $ax+by=n$ has a solution in positive integers $x,y$. (Take $(x,y)$ with $y \leq 0$ and $x$ minimal).
0
votes
1answer
218 views

Euler's Criterion and Wilsons Theorem

I am trying to prove: if $m = p_1p_2\cdots p_r$ with $2 < p_1 < \cdots < p_r$ prime, then $$x^2 \equiv 1\mod m$$ has $2^r$ solutions modulo $m$. I know Euler's Criterion: $p$ is an odd ...
0
votes
4answers
267 views

Solutions of the equation $ax+by=ab$

Let $a,b \in \Bbb N $ with $\gcd(a,b)=1$. The equation $ax + by = ab$ has the obvious solution $(b, 0)$ in integers. Show, however, that it has no solution in positive integers.
2
votes
1answer
69 views

Probability Factorization Algorithm

I want to prove the following: Let $n = pq$, with $p, q$ distinct odd primes. Let $x,y$ be random integers with $\gcd(xy, n) = 1$ and $x^2 \equiv y^2 \mod n$. Prove that there is a 50-50 chance that ...
0
votes
1answer
50 views

orders of elements and multiplicative inverse module m [duplicate]

Possible Duplicate: Find $ord_m b^2$ if $ord_m a = 10$ and $ab\equiv 1\pmod m$ If $ab \equiv 1 \pmod{m}$ and if $ord_ma=10$, find $ord_mb^{2}$. I know that $ab \equiv 1 \pmod{m}$ is used ...
0
votes
2answers
58 views

Use $\operatorname{ord}_{11}3$ to find remainder when..

Find $\operatorname{ord}_{11}3$. Then use what you found to find the remainder when you divide $3^{82}$ by $11$. Work thus far: $$\operatorname{ord}_{11}3=\ ?$$ $$3^1\equiv3\pmod{11}$$ ...
0
votes
1answer
860 views

Proving that floor(n/2)=n/2 if n is an even integer and floor(n/2)=(n-1)/2 if n is an odd integer.

How would one go about proving the following. Any ideas as to where to start? For any integer n, the floor of n/2 equals n/2 if n is even and (n-1)/2 if n is odd. Summarize: ...
0
votes
6answers
280 views

How to multiply decimal with wholenumber?

How Can I multiply x = (0.35)(80) x = 28 steps by step fastest way I am not going to lie, but it is time for me to take a test without using a calculator. Schools have made me worse by giving us a ...
1
vote
1answer
62 views

For any number $n \gt 1$ and all of its prime divisor $d_1, d_2, …$ s.t. $d_i \equiv 1 \pmod 3$ for each $i$, show:

For any number $n \gt 1$ and all of its prime divisors $d_1, d_2, ...$ s.t. $d_i \equiv 1 \pmod 3$ for each $i$ Show that the euler phi function $\phi(x) = 2n$ has no natural number solution.
0
votes
0answers
84 views

not sum of two squares

Let $m=r\cdot s$ where $m,r,s$ are natural numbers. Let us ascribe a number as re-presentable if it can be expressed as the sum of two squares in integers. We can prove, if any two of $m,r$ and $s$ ...
3
votes
1answer
130 views

The set $A = \{a^2 + 2b^2\mid a,b \in \Bbb Z\setminus\{0\}\}$

Let $A = \{a^2 + 2b^2\mid a,b \in \Bbb Z\setminus\{0\}\}$ and $p$ be a prime number. Prove that if $p^2 \in\ A$, then $p \in A$.
10
votes
2answers
252 views

If $\dfrac{4x^2-1}{4x^2-y^2}$ is an integer, then it is $1$

The problem is the following: If $x$ and $y$ are integers such that $\dfrac{4x^2-1}{4x^2-y^2}=k$ is also an integer, does it implies that $k=1$? This equation is equivalent to ...
8
votes
2answers
257 views

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? ...
1
vote
0answers
76 views

Pollard $p-1$ factorization

I need some help understanding this algorithm. I want to factor $n$. Suppose $n$ has a factor $p$ s.t. the primes that divide $p-1$ are less than $10,000$. And $p-1$ divides $10000!$. Let $m = ...
3
votes
1answer
405 views

Why there is this kind of relation between power and factorial?

What I am talking about is a fact, that if we write down n-th powers of consecutive natural numbers in a row, and then on the next row between each two numbers write their difference and repeat this ...
2
votes
2answers
46 views

Using the RSA system…

Using the RSA system with $(m,e)=(51,5)$ find a $d\ge1$ that will decode the messages. What I have so far (not sure if this is right): Since, $m=51$ and $e=5$ then the $\gcd(51,5)=1$ then: $$5d ...
1
vote
0answers
82 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
1
vote
4answers
111 views

Find $ord_m b^2$ if $ord_m a = 10$ and $ab\equiv 1\pmod m$

If $ab \equiv 1 \pmod {m}$ and if $ord_ma=10$, find $ord_mb^2$. Could somebody give me a hint? What I know is that $ab \equiv 1 \pmod {m}$ can be used when finding the multiplicative inverse. Would ...
0
votes
2answers
59 views

Give the remainder when..

Give the remainder when you divide $3*(16!)+2$ by $17$. I don't have much to go on, but i'm not asking you to simply give me the answer even though that would be great. Could someone show me where I ...
1
vote
0answers
54 views

Find the orders..

$\newcommand{\ord}{\operatorname{ord}}$ Find the orders below: \begin{align} & (a) \quad \ord_{11}5 \\ & (b) \quad \ord_{7}4 \\ & (c) \quad \ord_{23}22! \end{align} For the most part, I ...
0
votes
2answers
905 views

Find a multiplicative inverse…

Find a multiplicative inverse of $a=11$ modulo $m=13$. What is this saying? This seems like such a simple question, I just don't understand what it is asking for. An additional question related to ...
2
votes
2answers
295 views

Find all integer solutions to linear congruences

Find all integer solutions to linear congruences: \begin{align} &(a) &3x &\equiv 24 \pmod{6},\\ &(b) &10x &\equiv 18 \pmod{25},\\ \end{align} What I have so far: $$(a) ...
4
votes
4answers
2k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to proof it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
1
vote
2answers
323 views

Could you give me some small research questions in the university level?

I want to do some study about math in the university level, but i have no idea about choosing problems. The fact is that i try to take part in a research activity from our school, but when i got the ...
0
votes
1answer
112 views

What is the biggest positive integer within 100 that can be/can not be written as the differences between two positive primes?

What is the biggest positive integer within 100 that can be/can not be written as the differences between two positive primes? Can someone answer the cannot part? There are two parts in the ...
0
votes
1answer
90 views

Show the number of solutions

Show that the number of solutions of $x^2+y^2=m$, where $m=2^{\alpha}r$ and $r$ is odd, is given by $U(m)=4\sum_{u|r}(-1)^{\frac{u-1}{2}}=4\gamma(m)$, where $\gamma(m)$ denotes the number of positive ...
3
votes
3answers
350 views

Show $m^p+n^p\equiv 0 \mod p$ implies $m^p+n^p\equiv 0 \mod p^2$

Let $p$ an odd prime. Show that $m^p+n^p\equiv 0 \pmod p$ implies $m^p+n^p\equiv 0 \pmod{p^2}$.
1
vote
0answers
70 views

How difficult is to find x for x^2 mod N = a, where a = 1?

Is it any easier to find $X$ for $a=1$ than some other $a$'s that is smaller than $N$. $a$ is quadratic residue.