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

learn more… | top users | synonyms (1)

2
votes
0answers
41 views

Find the smallest number $n$ such that there exist polynomials $f_{1}, f_{2},…,f_{n}$ with rational coefficients

Find the smallest number $n$ such that there exist polynomials $f_{1}, f_{2},...,f_{n}$ with rational coefficients satisfying $$x^{2}+7=f_{1}(x)^{2}+f_{2}(x)^{2}+...+f_{n}(x)^{2}.$$ It's Olympiad ...
3
votes
1answer
37 views

What is the maximum possible value of $k$

What is the maximum possible value of $k$ for which $2013$ can be written as a sum of $k$ consecutive positive integers? I tried to write $2013$ as a sum of AP with common difference $1$ then ...
0
votes
0answers
17 views

Question about the sign of a certain sum

Given a modular form $f$ of an even weight $k$ for the full modular group. Let $\lambda_f(n)$ the $n$-th normalized Fourier coefficient of $f.$ For a fixed positive integers $a$ and $b,$ I want to ...
4
votes
0answers
54 views

Are all powers of 5 Friedman numbers?

Powers of 5 seem to have a quite interesting property. Not only do the all seem to be Friedman numbers in base 10, it also seems that they don't require digit concatenation and they their 'Friedman ...
3
votes
1answer
56 views

Maximize the Cyclic sum

Let $x_1,x_2,\dots ,x_6$ be nonnegative real numbers such that $x_1+x_2+x_3+x_4+x_5+x_6=1$, and $x_1x_3x_5+x_2x_4x_6 \geq \frac{1}{540}$. Let $p$ and $q$ be positive relatively prime integers such ...
1
vote
0answers
44 views

Solving quadratic congruences

System of equation is : $$ x^2 \equiv 2 \mod 3 $$ $$ x^2 \equiv 4 \mod 5 $$ So, if first equation doesn't have solution what should I do with it?
35
votes
1answer
1k views

Are there any Mersenne primes, besides 3, that end in 3

It's clear that Mersenne primes can't end in $9$, since $2^n$ can't end in $0$, but $2^n$ can end in $4$ and $2^{n}-1$ would end in 3. From the list at http://mathworld.wolfram.com/MersennePrime.html ...
1
vote
1answer
34 views

Divisibility proofs for greatest common divisor

I am studying divisibility and greatest common divisors. I have reached a section where I need to prove properties. My question is: are my proofs substantial? Or do I need to add to them? Below are ...
4
votes
2answers
84 views
0
votes
0answers
9 views

How to calculate and more importantly visualise Prefix Sum for an 3 , 4 and n-dimensional array?

I was trying to solve this problem . http://codeforces.com/problemset/problem/372/B I tried reading on http://wcipeg.com/wiki/Prefix_sum_array_and_difference_array but I still ...
0
votes
0answers
42 views

$x^2 + y^2 + z^2 = 2007^{2011}$ with $x$, $y$ and $z$ integers [duplicate]

Solve the equations $x^2 + y^2 + z^2 = 2007^{2011}$ in the set of integers.
0
votes
2answers
25 views

Minimum sum of factors of a natural number

Let's say I have a natural number $N$. $a$ and $b$ are two factors of $N$. How can I find $a$ and $b$ such that $a + b$ is minimum. Examples: $N = 12$, $a = 3$, $b = 4$ $N = 13$, $a = 1$, $b = 13$ ...
0
votes
1answer
29 views

Is this assertion about g.c.d. true? [closed]

Is it true that if $\gcd(a,bc)=1$ and $\gcd(b,c)=1$ then $\gcd(a,b^2)=\gcd(a,c^2)=\gcd(ab^2,c^2)=\gcd(a,(bc)^2)=1$? Many thanks.
1
vote
0answers
69 views

Proving that $b^6-2a^3b^3-2b^3+a^6-2a^3+1$ is never a nontrivial integer square?

I'm trying to prove that if $a,b$ are integers, and $b^6-2a^3b^3-2b^3+a^6-2a^3+1$ is a square [integer], then $ab=0$. What general tools are available to attack such a problem?
0
votes
0answers
30 views

Natural Number Decomposition [duplicate]

Given an arbitrary natural number $n$ , in how many ways can we write it as the sum of consecutive natural numbers? Is there any closed form answer in terms of $n$? Example: if $n=270$ then it can be ...
2
votes
0answers
78 views

Is there a formula for $1+\sqrt{2}+\sqrt{3}+\cdots+\sqrt{N}$? [duplicate]

Is there a known formula to the sum $$1+\sqrt{2}+\sqrt{3}+\cdots+\sqrt{N}$$ where $N$ is some natural number? Thanks
0
votes
2answers
43 views

Which numbers are square modulo 9? [closed]

How can I prove that n = $1,4,7,9$ for every integer k such that $k^2 = n$ (mod9)?
5
votes
1answer
52 views

Prove that $(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$

I'm working through Oystein Ore's Number Theory and its History. On p. 109, I'm stuck on #2. The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: ...
3
votes
3answers
67 views

A puzzle about numbers which do not have 2 in their decimal representation

I came across this puzzle recently which I hope people might enjoy. Let $S(n)$ be the set of positive integers less than $n$ which do not have a $2$ in their decimal representation and let ...
3
votes
1answer
38 views

An interesting fact about the number 123456789 and its generalization in arbitrary base

The number $(12\ldots(b-1))$ in base $b$ has the property that when multiplied by any integer $1\le k\le b-1$ which is coprime to $b-1$, its digits are permuted. Why? For example in base 10, ...
-4
votes
2answers
44 views

Making a Perfect square [closed]

How to get max value of $-2x^2+3x+5$ by making perfect square. I got wrong ans. Correct ans. Must be $49/8$.
0
votes
0answers
29 views

For a given $n$, under what condition(s) there exists (at least) two different $c$ and $c'$ such that $X_n^c=X_n^{c'} $?

Let $X_n^c=\{\cos\left((4k-c)\frac{\pi}{2n}+\frac{\pi}{4}\right): k=0, 1, \dots, n-1\}$ where $c\in\{0, 1, \ldots, \lfloor\frac{n}{2}\rfloor\}$ and $n$ is any positive integer greater than 3. I want ...
9
votes
1answer
87 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $\mathbf {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither ...
6
votes
3answers
182 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ...
1
vote
1answer
42 views

If $\varphi(mn)=\lambda \varphi(m)\varphi(n)$ what should be written for $\lambda$

Respected All. I am studying number theory where I came to know that $\varphi(n), \sigma(n)$ both are multiplicative function ; In other words, if $(m,n)=1$ then \begin{align} ...
1
vote
3answers
39 views

What is the smallest possible natural number $𝑛$ for which $x^{2}-nx+2014=0$ has integer roots?

What is the smallest possible natural number $𝑛$ for which the equation $x^{2}-nx+2014=0$ has integer roots? My idea was, If the roots are integers, then they are the divisors of $2014$, I don't ...
3
votes
0answers
48 views

Debunking an elementary proof of FLT

José Cayolla: Fermat's Last Theorem admits an infinity of proving ways and two corollaries. arXiv:1507.06989 [math.GM] I don't usually devote so much time to "crackpot papers", but I have a ...
7
votes
1answer
75 views

Find the least positive integer $n$ so that $\left ( 1-\frac{1}{s_{1}} \right ) \cdots \left ( 1-\frac{1}{s_{n}} \right )=\frac{51}{2010}$

Find the least positive integer $n$ for which there exists a set $\left \{ s_{1}, s_{2},....,s_{n} \right \}$ consisting of $n$ distinct positive integers such that $$\left ( 1-\frac{1}{s_{1}} ...
1
vote
2answers
38 views

Proving that $\text{gcd}(a,b)=\text{gcd}(b,r)$

Let $0\neq a,b\in \mathbb{Z}$. there are integers $p,q$ such that $0\leq r<b$ and $a=bq+r$. Prove that $(a,b)=(b,r)$ My attempt: $$\text{gcd}(a,b)=\varphi$$ So $$\exists \,m,n \in ...
0
votes
1answer
19 views

Find the maximum sum of real part roots

Let $z_1,z_2,z_3,\dots,z_{12}$ be the 12 zeroes of the polynomial $z^{12}-2^{36}$. For each $j$, let $w_j$ be one of $z_j$ or $i z_j$. Then the maximum possible value of the real part of ...
-2
votes
1answer
23 views

How does this proof on quadratic congruences make sense?

Could I get some help with this proof? It is supposed to be induction, but I have no idea where the $m \tilde {x_0} \frac 12 (p+1)p^k$ term near the bottom comes from. I understand how it is used for ...
0
votes
0answers
20 views

Trigonometric functions on set of co-primes to $n$

E.g. I plotted the function values of $y=\tan(x\frac{\pi}{n})$ for integer $x$-values in the range of $0,\cdots,n$ where $n$ is a given odd integer ( to prevent the case of undefined ...
-5
votes
2answers
36 views

number theory quest. [closed]

A positive integer "$n$" is called a magic number if it has the following property: if $a$ and $b$ are two positive numbers that are not coprime to $n$ then $a+b$ is also not coprime to $n$. For ...
-2
votes
1answer
32 views

Every positive even integer can be written in the form $4q$ or the form $4q+2$ [duplicate]

Show that any positive even integer is of the form 4q or 4q+2 where q is a whole number. I am trying to use division algorithm or something to show this. I want to know how Euclid's lemma can be ...
4
votes
3answers
102 views

Prove $\log_7 n$ is either an integer or irrational

I have been trying to prove a certain claim and have hit a wall. Here is the claim... Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational Proof ...
-1
votes
2answers
32 views

How many ways to arrange colors (constraints)

Ed has five identical green marbles and a large supply of identical red marbles. He arranges the green marbles and some of the red marbles in a row and finds that the number of marbles whose right ...
2
votes
4answers
67 views

Number of Interesting Quadruples

Define an ordered quadruple of integers $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$, and a+d>b+c. How many interesting ordered quadruples are there? This is a bit of trouble ...
2
votes
1answer
63 views

strange fibonacci recurrence

As it is well known fibonacci numbers satisfy the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ with initial conditions $F_{0}=0$ and $F_{1}=1$. While playing around with numbers,I noticed the ...
0
votes
0answers
40 views

What is Lebesgue measure of sets of inverse prime numbers in $[0,1] $?

I would like to know if it is possible to know the lebesgue mesure of sets of inverse prime numbers in $[0,1]$ Note : I think should to know in the first if the sets of primes are infinit countable ...
2
votes
1answer
50 views

Prove that $4$ divides $n$ [duplicate]

Let $a_1$,$a_2$,$a_3$,.......,$a_n$ be $n$ such that each $a_i$ either $1$ or $-1$.If $a_1 a_2 a_3 a_4+a_2 a_3 a_4 a_5+......+a_n a_1 a_2 a_3=0$, then prove that $4$ divides $n$. I tried this for ...
1
vote
2answers
83 views

Is $2^n-1$ always a prime for odd values of $n$? [duplicate]

Is $2^n-1$ always a prime for odd values of $n$? $n\not=1$ Taking some odd values of $n$, I observed outcome is coming as a prime number. How to verify it? Or at-least, is $2^n-1$ always coprime to ...
0
votes
1answer
38 views

if $n > 1$ is an integer not of the form $6k + 3$, prove that $n^2 + 2^n$ is composite.

My proof. By Division Algorithm, n is one of form $6 k, 6 k+1, 6 k+2, 6 k+4, 6 k+5$. So first, If $n=6 k$, $n^2+2^n=36 k^2+2^{6 k}$. then $2$ divide it. and, divisor is not one. so, it is composite. ...
2
votes
2answers
40 views

Show that 7 is a primitive root modulo 601

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.
2
votes
2answers
36 views

Prove that either the average of the numbers $a_{1}, a_{2},…, a_{n}$

Let $a_{1}, a_{2},..., a_{2n}$ be positive real numbers such that $a_{j}a_{n+j}=1$ for the values $j=1,2,...,n$ ($a$) Prove that either the average of the numbers $a_{1}, a_{2},..., a_{n}$ is ...
3
votes
1answer
33 views

Prove for primes p $>2$ that $\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\frac{1}{2}p(p+1)\pmod {p^2}$

Let $p$ be an odd prime. Prove that: $$\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\dfrac{p(p + 1)}{2}\pmod {p^2}$$ The problem is taken from the 2004 Canada National Olympiad. I am only able to show ...
115
votes
20answers
9k views

Mental Calculations

This is the famous picture "Mental Arithmetic. In the Public School of S. Rachinsky." by the Russian artist Nikolay Bogdanov-Belsky. The problem presented on a blackboard requires computing the ...
0
votes
1answer
80 views

Least prime number proof [closed]

Prove that 2 is the only even prime number. I know that 2 is the only even prime number. I am curious to prove it
-1
votes
2answers
40 views

Last digit of a perfect square must be $0, 1, 4, 5, 6,$ or $9$ [closed]

We know that a perfect square number can contain 0,1,4,5,6 and 9 in its unit place. How can I prove that a perfect square number cannot contain 2,3,7 and 8 in its unit place?
1
vote
1answer
41 views

Is my proof for this fact correct?

The thing ought to be proven Let $a$ and $b$ be nonzero integers that are relatively prime, and let $c$ be an integer. Show that $ax+by=c$ has an integer solution. My postulated proof that ought ...
0
votes
3answers
41 views

Prove n is a product of a square and a cube

Suppose $n\ge 2$ is an integer with the property that whenever a prime $p$ divides $n$, $p^2$ also divides $n$ (i.e., all primes in the prime factorization of $n$ appear at least to the power ...