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

learn more… | top users | synonyms

0
votes
1answer
39 views

How many times must you square a number to get $<1/2$

Let $0\leq x<1$. Be given. How many times must you square $x$ to get less than $1/2$? Clearly this depends on $x$. But is there a nice formula to determine this? Such as: To make ...
1
vote
2answers
24 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
3
votes
2answers
36 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
1answer
14 views

Division Algorithm With Negative and Absolute Value

(a) Prove that $d \, |\, a$ implies that $d \,| (−a)$. (b) Prove that $d\, |\, a$ if and only if $d \,| (−a)$. (c) Prove that $d \,|\, a$ if and only if $d\, \Big|\, |a|$. I can see why these ...
1
vote
1answer
34 views

How do you solve $k(a^2-b^2)=2(ax-by)$?

let $a,b,c,d,x,y,k$ be all non-zero positive integers >1. If $a^2-b^2 \neq0$,how do you find all the pairs $(x,y)$ such that $k(a^2-b^2)=2(ax-by)$. I have found so far only solutions where ...
1
vote
3answers
36 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
0
votes
1answer
18 views

Hilberts Theorem (norm group)

The theorem says the following: The map $N$ is a group homomorphisim from the multiplicative group of $\mathbb{Q}^{x}[i]$ to the multiplicative group of $\mathbb{Q}^{x}$ and has kernel $\lbrace ...
0
votes
2answers
69 views

When is the product $(1+1/3)\cdots(1+1/n)$ equal to an integer?

It looks like its never the case. Is that right?
1
vote
2answers
20 views

Prove that if $\gcd(a,n)=1$, then the integers $c,c+a,c+2a,\ldots,c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$

I am guessing I need to show that the given integers equal $0,1,2,\ldots, (n-1)$ mod n taken in some order. However I am not sure on how to start, Any help ?
2
votes
0answers
27 views

The digit 3 and 2 digit number question

The digit 3 is written at the right of a certain 2-digit number forming a 3-digit number. The new number is 372 more than the original 2-digit number. What is the sum of the digits of the original ...
1
vote
3answers
44 views

Part of a proof that the product of an odd and even integers is even

I'm practicing for a test on Monday and I'm trying to do some proofs - but I'm not entirely sure if this is sufficient enough for the question. "Prove that for all integers, m and n, if m is odd and ...
0
votes
0answers
9 views

Looking for general proof of a sum of an additive form of elementary symmetric polynomials

For sake of avoiding complicated general formulation I try to formulate in the special case of a set of 3 numbers $M=\{a_1,a_2,a_3\}$ with e.g. $a_i\in\mathbb R$. The sum I am looking for is in this ...
0
votes
2answers
52 views

Making 24 with given number N

Initially we have a sequence of n integers: 1, 2, ..., n. In a single step, we can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, ...
1
vote
3answers
108 views

Look at the following infinite sequence: 1, 10, 100, 1000, 10000, . . ..

What is the proof that there are 2 numbers in this sequence that differ by a multiple of 12345678987654321?
0
votes
1answer
28 views

How can we show that $\pi (x) \leq \frac{x}{2}+1$?

What is the proof that the prime counting function $\pi (x)$ is such that $$\pi (x) \leq \frac{x}{2}+1$$
1
vote
0answers
52 views

Mordell Diophantine: $x^2+11=y^3$

I've been trying to solve the diophantine $$x^2+11=y^3$$ recently but to no avail. I tried the "UFD trick", re-writing as $(x-i\sqrt{11})(x+i\sqrt{11})=y^3$, but it didn't give me all the solutions. I ...
2
votes
3answers
27 views

Remainder problem when dividing numbers

The number x is a positive integer < 100. When x is divided by 7, the remainder is 2, and when x is divided by 10 the remainder is 8. What is the value of x? Is there a formula to solve this type ...
0
votes
1answer
40 views

If $\gcd (a,0)=1),$ what can a possibly be?

I feel like a could be any number, but $0$ could divide any number,so they won't be mutually exclusive. I'm not sure, maybe this is not related, but it just confused me.
0
votes
0answers
28 views

Number 36 in base 4/5

In my curse of number theory I need write the integer number 36 in base $4/5$. I have been researching how to do it but do not make it yet. Appreciate if you can help me
0
votes
0answers
7 views

How to show that $f$ is Completely multiplicative function

If $f$ is a multiplicative function and $(f\cdot \mu^{-1})^{-1}= f\cdot \mu$. Prove that $f$ is a is completely multiplicative function. $\mu$ is the Möbius and $\cdot$ is the simple product.
1
vote
1answer
25 views

Finding a nontrivial solutions in natural numbers.

Consider the equation for natural numbers $i,j,k,l:$ $$ (j^2-i^2) (k\cdot l)^2=2\, (l^2-k^2) (i\cdot j)^2. $$ I am trying to prove that it has no solution. To undertand why, let us first consider ...
4
votes
4answers
252 views

Solving Diophantine equations involving $x, y, x^2, y^2$

My father-in-law, who is 90 years old and emigrated from Russia, likes to challenge me with logic and math puzzles. He gave me this one: Find integers $x$ and $y$ that satisfy both $(1)$ and $(2)$ ...
6
votes
4answers
845 views

Can any two irrational numbers NOT of the form (m+A) and (n-A) be added to produce a rational number?

$m$ and $n$ being rational numbers, A being an irrational number. I was wondering if two irrational numbers when added always yield an irrational number. All the counter-examples I could find were of ...
0
votes
3answers
52 views

How can we find the smallest number n such that 2^(2^n) + 1 is not a prime.

How can we find the smallest fermat number that is not prime and show that it is indeed not a prime? Yes, when n=5, it is not a prime. How can we find n=5 , other than just factoring the fermat number ...
1
vote
0answers
36 views

Count the strings with n0 K zeroes together

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1. Now , the problem is we need to count the number of ways to fill these ...
0
votes
1answer
43 views

Prime factorization of 2^(16) - 1

Trying to show the the prime factorization of $$2^{16}-1$$ without a calculator. I know that $2^{16} - 1$ yields the prime numbers$$3*5*17*257$$ because I calculated $2^{16}-1$ on my calculator ...
1
vote
1answer
47 views

Sum over divisors of sum over coprimes

Set $n \in \mathbb{N}$ , $n>1$ . Consider the function $\phi_{1}$ as $$\phi_{1}(n)= \sum _{r=1 \atop \gcd(r,n) =1}^{n} r$$ Prove that $$\sum_{d|n} d \cdot \phi_{1}\Big(\frac{n}{d}\Big) = ...
2
votes
2answers
91 views

$2^{8420} - 9$ is prime or not

How to prove $2^{8420} - 9$ is or isn't a prime number? I tried modding it by 10 to get the last digit, but that's a 7 which doesn't help. We've only been covering successive squaring in this ...
2
votes
1answer
27 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
40 views

$\sqrt {-6}$ is not prime in $\mathbb{Z}+\mathbb{Z}\sqrt {-6}$

Suppose $\sqrt{-6}|(a+b\sqrt{-6})(c+d\sqrt{-6})$. I need to show that $\sqrt{-6}$ does not divide $(a+b\sqrt{-6})$ and does not divide $(c+d\sqrt{-6})$. I thought you might arrive at some ...
0
votes
4answers
29 views

Let $p \geq 5$ and prime. Show $p^2 + 2$ is divisible by three.

I know I have to use the division algorithm to put into the form $p^2 + 2 = 3q + r$ but everything I've tried after that has lead me to a dead end. I've mainly been trying to show $r=0$ or to make the ...
0
votes
1answer
35 views

Concatenating squares - is this solution unique?

This question asks about concatenated squares to make a square number. For example $[4][9]=49, [16][9]=169, [3136][441]=3136441, [64][009]=64009$ I've been doing a bit of investigating for the case ...
1
vote
1answer
30 views

Best self study book with answers to selected questions for analytic number theory?

All: Can anyone recommend Best self study book with answers to selected questions for analytic number theory ? If a book have no answers to questions, but if you know if some professors choose the ...
2
votes
2answers
31 views

Prove that if $\gcd(a,b)=1$ then $\gcd(a^m, b)=1$

I am using the Euclidean Algorithm (EA) for proof. Let $a>b$ and by EA we have $$ \begin{align} a=q_0 b+r_1 & & & \text{where }0\leq r_{1}<b \\ b=q_1 r_1+r_2 & & & ...
1
vote
0answers
23 views

looking for origin of number theory problem on 4x-floor-sqrt (maybe IMO)?

this problem was recently posed by BS in the number theory chat room. he thinks it may originate from the International Math Olympiad & he says he has a solution. has anyone seen it there? looking ...
1
vote
0answers
20 views

Prove that this sequence of fractions is returned unchanged after the divisor recurrence, the matrix inverse, and the sum over divisors.

Consider the fraction of binomial coefficients and powers of $4$: $$a(n)=\frac{\binom{2 (n-1)}{n-1}}{4^{n-1}}$$ starting: ...
0
votes
3answers
34 views

Modular calculus and square

I want to prove that $4m^2+1$ and $4m^2+5m+4$ are coprimes and also $4m^2+1$ and $4k^2+1$ when $k\neq{m}$ and $4m^2+5m+4$ and $4k^2+5k+4$ when $k\neq{m}$. Firstly : Let $d|4m^2+1$ and $d|4m^2+5m+4$ ...
2
votes
2answers
70 views

Prevent similar consecutive colours for a pie chart

Background Calculating colours for pie chart wedges. Consider: $$ \begin{align} d(n)&=\frac{\theta}{t}\times n\\ \end{align} $$ Where: $\theta$ is the degrees in a circle (360) $t$ is the ...
12
votes
6answers
971 views

Is there any book/resource which explain the general idea of the proof of Fermat's last theorem?

I look for a book/resource which display the general idea of the proof of Fermat last theorem in a simple manner for the public. I mean, books which is not for mathematicians but for the general ...
1
vote
2answers
47 views

what does the phrase “no zero divisors mod 13” mean?

I came across this while trying to work a problem : What is a "zero divisor" and how are they able to use zero product property as if it is an algebraic equation ? Highly appreciate any help ! ...
0
votes
2answers
24 views

replacing numbers to get final anser

I found this question in a random problem solving book that I was reading and wanted to know how you would solve it. I am not sure as how to go about this. Take any positive integer $n$ with fewer ...
1
vote
1answer
43 views

Find all the triples $(x,y,z)$ such that $ax+by=cz$

Let $a,b,c,x,y,z >1$ if $\gcd(a,b,c)=1$, find all the non-trivial triples of positive integers $(x,y,z)$ such that $ax+by=cz$. Progress I have been struggling finding the solutions. At first, I ...
1
vote
0answers
37 views

Which numbers have the sum of their digits equal to the sum of the digits of their inverse?

$n$ is a number such as $n \in \mathbb{N}$ and $n >0$.(Eg. $n = 8$) $p$ is the sum of the digits of $n$ in base $10$.(Eg. $n=80$, $a = 8+0 = 8$) $q$ is the sum of the digits of $1/n$ in base ...
0
votes
1answer
33 views

Number of integer lattice points within a circle

I am trying to solve a problem on codeforces, to be precised, this problem. I was able to figure out that the solution is $N(n) - N(n-1)$ where $N(n)$ is the number of lattice points withing a circle ...
2
votes
1answer
49 views

Number theory problem from 11th Iberoamerican olympiads

Given a number $n \in \mathbb{N}$, such that $n>1$, let us consider all the fractions of the form $1 \over{ab}$, where $a$ and $b$ are coprime natural numbers such that $0<a<b \leq n$ and ...
3
votes
4answers
49 views

Are all those numbers coprime?

The values of $4m^2+1$ and $4m^2+4m+5$ for $m\geq{1}$ are (resp.) 5,17,37,... and 13,29,53,... Those numbers seem to be all coprime : how to prove it if it is true, please ?
0
votes
1answer
86 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
0
votes
2answers
33 views

finding values of $x$ in $Z$

Find all values of $x$ such that $\frac{x-4}{2x-3}\in\mathbb Z$? I came up with this question to see if it could be solved based on some other questions I did myself. I thought this could not be ...
2
votes
1answer
40 views

How to solve $n$ in $5^{n-1}\equiv 1 \pmod{n}$

$5^{n-1}\equiv 1 \pmod{n}$ I see that this holds true when $n$ is prime by Fermat's little theorem. However there could be few composite numbers, $n$ for which the congruence might hold true ? How to ...
1
vote
0answers
21 views

Find the reflection point $P$

On the real number line, paint red all points that correspond to points of the form $81x+100y$, where $x$ and $y$ are positive integers. Paint the remaining integer points blue. Find a point $P$ on ...