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

learn more… | top users | synonyms

0
votes
1answer
175 views

How many numbers are there which are less than 100 and can be expressed as sum of three of their factors?

I know the answer is 16. I.E all the multiples of 6, but what is the actual concept behind this? I was trying to understand an explanation given by Euler, but in vain. Kindly explain in layman terms. ...
8
votes
1answer
2k views

Is greatest common divisor of two numbers really their smallest linear combination?

In a lecture note from MIT on number theory says: Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear combination of a and b. For example, the greatest ...
1
vote
1answer
48 views

Radix representation and a congruent relation

Let $\epsilon_p(n)=\lfloor {n/p}\rfloor+ \lfloor {n/p^2}\rfloor+\cdots$ i.e the largest poswer of $p$ (prime) that divides $n!$ where $n$ is an integer. Let $(\alpha_0\ldots\alpha_m)$ be a ...
1
vote
2answers
70 views

Prove that if $a \equiv b \pmod{3}$, then $2a \equiv 2b \pmod{3}$.

A friend and I are completely stumped on this prompt, and are even having trouble seeing how its statement is true. Any help will be appreciated! Prove that if $a \equiv b \pmod{3}$, then $2a \equiv ...
1
vote
1answer
124 views

Bounds for Waring's Problem

The question is posed as such: If G(k) = min{ g : every "sufficiently large" natural number can be written as the sum of g kth powers } Then I seek to prove two things. First, to establish the ...
0
votes
3answers
102 views

Find a number $x<100$ that satisfies three congruences.

Find a number $x<100$ for which all three statements are true: When $x$ is divided by $3$, the remainder is $2$. When $x$ is divided by $4$, the remainder is $3$. When $x$ is divided by $5$, the ...
8
votes
3answers
218 views

$a+b=c \times d$ and $a\times b = c + d$

There is a 'nice' relationship between the integers (1,5) and (2,3) as $$1+5=2 \times 3;$$ $$1\times 5 = 2 + 3.$$ So I tried to find all positive integers pairs $(a, b)$ and $(c, d)$ such that ...
3
votes
1answer
274 views

Bounding the finite sum of $\frac {\log n}{n}$

So I'm completely lost in my class on Additive Number Theory. I've been trying to show that there exists a constant B such that $$\sum_{n \le x}\frac{\log n}{n} = \frac{1}{2}\log ^2x + B + ...
0
votes
1answer
546 views

Using Partial Summation

So here's a problem I've been working on for some time. Define $\gamma$ as $$ \gamma = 1-\int_1^\infty \frac{f(t)}{t^2} dt\,. $$ where $f(t) = t - [t]$ What I'm trying to show (unsuccessfully) is ...
2
votes
1answer
78 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
68 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
297 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
166 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
160 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
330 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
241 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
314 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
144 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
185 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
207 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
264 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
834 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
273 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
83 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 ...
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 = ...
2
votes
1answer
374 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
44 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 ...