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

learn more… | top users | synonyms (1)

4
votes
1answer
36 views

Area of the lattice generated from $(n, n\sqrt{2} \mod 1)$

I plotted $\Big\{ (n, n \sqrt{2} \, \mathrm{mod} \,1) \;\Big| -50 \leq n \leq 50 \Big\}$ and even though the $n \sqrt{2}$ is a line, the pattern that emerges is a lattice. What is the basis of this ...
1
vote
2answers
20 views

Is this condition necessary for two numbers to be coprime?

Using Euclidean Algorithm, one could show that, suppose $hcf(x,y)=1$ then $ax+by=1 \ \text{for some} a,b \in \mathbb Z$ But is it true that if two numbers $x,y$ satisfy $ax+by=1 \ \text{for some} a,b ...
4
votes
2answers
127 views

for which positive integer $m$ does $(ab)^{2015} = (a^2 + b^2)^m$ have positive integer solutions [closed]

For which positive integers $m$ does the equation $(ab)^{2015} = (a^2 + b^2)^m$ Have positive integer solution ?
1
vote
1answer
20 views

how to prove this fraction is at its lowest terms?

I was asked to prove that $\frac{a^3+2a}{2a^4+5a^2+1}$ is in its lowest terms. I tried by classifying the situation according to whether $a$ is odd or even, and find that the nominator and the ...
1
vote
2answers
55 views

How to find the rightmost 25 digits in $100!$?

The question is Find the rightmost 25 digits in decimal expansion of $100!=1\times 2\times \dotsb \times100$ By counting the number of fives in the prime factorisation of $100!$, I know there ...
1
vote
0answers
23 views

Finding the value of a sum of two Hecke eigenvalues

I did some computations but I am stuck in finding the exression of the sum $$\lambda_f(n^2)+\lambda_f(n)^2 $$ in terms of $\lambda_f(n),$ where $f$ is a modular form for the full modular group. Any ...
-3
votes
2answers
40 views

Checking Divisibility [closed]

If $3$ consecutive positive integers sum up to an even number,then which of the following DEFINITELY counts the product of these numbers? $a)3 \ $ $ b)4 \ $ $c)5 \ $ $ d)7 \ $ Give ...
19
votes
2answers
148 views
+50

For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$. Let $n\ge 2$ be a positive integer. Show that there ...
0
votes
1answer
68 views

Probability of hitting a number $Ib$ (rare case)

Consider a set $S$ of $N^{3/2}$ numbers. Fix a collection $T$ of $N^{\frac{1}{2}}$ numbers. With every trial, we have the freedom to choose $N^{1-\epsilon}$ of them at a time without overlapping. My ...
4
votes
1answer
63 views

In what system(s) of numeration is 11111 a perfect square?

From Charles Trigg's "Mathematical Quickies: 270 Stimulating Problems with Solutions": In what system(s) of numeration is 11111 a perfect square? I have found one base that works: 3. I am not ...
1
vote
2answers
61 views

The difference between Z(G) and C(a) in an example

I found that I didnt understood the defenitions. I have this exercize: to prove that $a\in Z(G)$ $<==>$ $C(a) = G$ Is there here something to prove? Isnt it directly of their defenitions ? I ...
0
votes
1answer
34 views

Find the number of sets satisfying the conditions

Let $ N$ be the number of ordered pairs of nonempty sets $ \mathcal{A}$ and $ \mathcal{B}$ that have the following properties: • $ \mathcal{A} \cup \mathcal{B} = ...
0
votes
3answers
58 views

If $|x -4 | + |y - 4| =4$ then how many integers value the sets (x,y) have?

Given If $|x -4| + |y - 4| =4$ then how many integers value the sets $(x,y)$ have? $x$ and $y$ are both positive and negative numbers. options a)infinite b)$3$ c)$5$ d)$12$ e)$16$ ...
2
votes
1answer
107 views

Show that $n$ does not divide $2^n - 1$ where $n$ is an integer greater than $1$?

Clearly $2^n - 1$ is an odd integer, therefore, let $n$ be an odd integer and it divides $2^n - 1$. We can write $2^n - 1 = (2-1)(2^{n-1} + \cdots \cdots + 1) = (2^{n-1} + \cdots \cdots + 1)$ From ...
1
vote
1answer
58 views

Must a solution of $x^2 + 4y^2 = p$ be unique

Let $p$ be prime with $p = 4k + 1$. Has the equation $$ x^2 + 4y^2 = p $$ for $x,y \in \mathbb N$ at most one solution?
2
votes
0answers
34 views

How many “near-Fermat triples” are there?

Is the following statement true? Claim For every $n\in \mathbb N$, there is a constant $d$ such that there are infinitely many triples $a,b,c \in \mathbb N$ with $$ | a^n + b^n - c^n | ...
0
votes
0answers
22 views

Probability of hitting a number - $\mathsf{II}$

Suppose you have $\frac{cn}{(\log c+\log n)^a}$ distinct pairs of numbers where fixed $c,a$ satisfies $1<c,a<\infty$. You are to choose two sets of $\frac{4\sqrt{n}}{(\log n)^b}$ distinct pairs ...
1
vote
2answers
27 views

The number of numbers whose digits are different and add up to 36

All the digits of a number are different, the first digit is not zero, and the sum of the digits is 36. There are N × 7! such numbers. What is the value of N? How should I approach this problem? ...
1
vote
3answers
30 views

What can you say about a number with remainder 1 and 2 when divided by 3 and 4 respectively?

I was trying to solve a problem which states: How many two-digit numbers have remainder 1 when divided by 3 and remainder 2 when divided by 4? and solved it by writing down individual numbers... ...
2
votes
3answers
54 views

Proof of the irrationality of $\sqrt n$, where $n$ is square free

I am trying to review some old algebra, and in particular I wanna show that $\sqrt2$ is irrational Since integers are the only integral elements of $\mathbb Q$ over $\mathbb Z$, assume $r=\sqrt 2$ is ...
2
votes
0answers
40 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
52 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
33 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
83 views
0
votes
0answers
8 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
65 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 ...
5
votes
1answer
159 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
36 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
17 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 ...