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

learn more… | top users | synonyms (1)

0
votes
0answers
79 views

Monotonically decreasing function for multiplication product?

I have a set of numbers $S = [100,999]$ for which I want the maximum product $p$ such that $p = a \times b$ for all $a,b \in S$ also fulfilling some condition $C$. I would like $p$ to be monotonically ...
1
vote
3answers
32 views

How to find the greatest integer, j, such that j * ( j - 1 ) / 2 < k?

How to find the greatest integer, j, such that j * ( j - 1 ) / 2 < k ? Is there a way to find a formula for j in terms of k ? Thanks in advance.
1
vote
5answers
117 views

Proving $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ [duplicate]

I'm trying to prove by MI. I have already distributed n+1, but now I'm stuck on how I can show 9 divides the RHS since $42n$ and $3n^3$ does not divide evenly. ...
3
votes
3answers
47 views

Prove $n^2 − 4n = 8t + 5$ for some integer t. [closed]

I am stuck on this proof. Any help is appreciated. I am trying to prove the following statement. Let n be any odd integer. Prove $n^2 − 4n = 8t + 5$ for some integer t.
3
votes
2answers
67 views

When does $n$ divide $\binom{n}{i}$ for all $i$?

For what $n$ is it true that $n$ divides $\binom{n}{i}$ for all $i=1,2,\ldots,n-1$? When $n$ is prime, the statement is true, which we can see by looking at the expansion of $\binom{n}{i}$. But what ...
5
votes
2answers
182 views

finding the difference of perfect squares

Find the difference between the smallest perfect square larger than one million and the largest perfect square smaller than one million. I did not want to use a calculator for this question. I ...
2
votes
3answers
182 views

Proving that the square root of 5 is irrational

Prove that $\sqrt{5}$ is irrational. I begin with the identity $(\sqrt{5} + 2 )(\sqrt{5} - 2 ) = 1$. Then I am told to extract $\sqrt{5}$ from the first or second factor and consider it to be ...
16
votes
3answers
557 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
3
votes
2answers
244 views

Find all primes of the form $2^{2^n} + 5$ for a nonnegative integer n

I'm a little lost on how to do this problem. It looks a lot like the definition for the Fermat numbers: $F_n = 2^{2^n} + 1$, however I'm not sure how to use that in order to find all of the primes of ...
1
vote
1answer
38 views

Basic question regarding addition in $p$-adic integers

I just learned $p$-adic integers and I am confused about something. I was wondering if someone could possibly explain me how it is done. Suppose I have $\bar{a} = 1 + 0 \cdot p + 0 \cdot p^2 + 0 ...
3
votes
1answer
92 views

Biggest set such that sum of any pair is perfect square

What is the biggest set of positive integers such that the sum of any pair of them is a perfect square? (Or can we construct an infinite such set?) One such set of size $3$ is $\{6,19,30\}$, which ...
8
votes
2answers
442 views

Olympiad problem: Erdos-Selfridge

The following problem is a special case of Erdos-Selfridge theorem: http://projecteuclid.org/euclid.ijm/1256050816 Problem: Prove that for any positive integer $n$, the product $(n+1)(n+2)...(n+10)$ ...
2
votes
1answer
19 views

Reducing Common Denominator

I have this pie chart which needs to show a break down of the total time spent. I.e. where the time is being spent. So I have these times in ms: ...
1
vote
1answer
55 views

Prove that a sum of squares is a CSR modulo prime [duplicate]

How can I prove that a sum of two integer squares, namely $ x^2 + y^2 $ (ranging from $ x = 0 \to p, \; y = 0 \to p $) is a complete system of residues (CSR) modulo $ p $ (prime)? Or, how can I prove ...
8
votes
1answer
183 views

Numbers represented as two different sums of squares

This is an interesting question I came across, and it does not look that easy: $365$ can be written as a sum of $2$ consecutive squares and also $3$ consecutive squares: $$ \large 365 = 14^2 ...
0
votes
2answers
53 views

Number of integer solutions of two similar equations

Find the number of integer solutions of: (a) $${1\over\sqrt{x}}+{1\over\sqrt{y}} = {1\over\sqrt{20}}$$ (b) $${1\over\sqrt{x}}+{1\over\sqrt{y}} = {1\over\sqrt{2014}}$$ I know the ...
0
votes
1answer
45 views

Find the number of primes between $n$ and $n!$

Question Prove that between $n$ and $n!$ there are at least $n$ different primes. I don't know how to approach to this problem
2
votes
0answers
76 views

Enumerating n-gon rings

How many rings can be constructed from a set of regular $n$-gons? For this purpose a ring is planar arrangement of $m \ge 2$ identical non-overlapping regular $n$-gons joined edge to edge, the whole ...
5
votes
1answer
178 views

Problems in elementary number theory and methods from physics

I was wondering if there are intuitive "physical" arguments to solve problems from number theory (elementary number theory in particular, but also advanced topics). To make an example, a proof of ...
2
votes
2answers
93 views

Minimum sum of set whose average of subsets is positive integer

A finite set of positive integers $A$ is called meanly if for each of its nonempty subsets the arithmetic mean of its elements is also a positive integer. In other words, $A$ is meanly if ...
1
vote
2answers
42 views

What is the order of each element in $\mathbb{Z_4}$?

I understand that for each $x \in \mathbb{Z_4}$ we're trying to find the smallest $k$ such that $x^k \equiv 1 \mod 4$. So we have $x = 0$ to begin with, but $0^n \mod 4$ for any positive integer $n$ ...
0
votes
4answers
67 views

Show that some group is isomorphic to $\mathbb{Z_n}$

If $G$ has order $4$ and has an element of order $4$, then $G$ is isomorphic to $\mathbb{Z_4}$. Can someone briefly explain why this is true? I understand that $|G| = 4$, but I don't understand ...
2
votes
1answer
169 views

Distinct elements in the Union and Intersection of A and B

Take a set $x$ with $10$ distinct elements. Rule: Everytime you have two subsets, $A$ and $B,$ you also have $A\cup B$ and $A \cap B.$ What is the maximum number of subsets you can have such ...
0
votes
3answers
60 views

This is a question about elementary number theory

the integer 220, 251 304 represent three consecutive perfect squares in base b. Determine the value of b.
1
vote
0answers
34 views

Set whose average of subsets is always square (cube, etc.)

Fix $n>1$. Is there a set $A$ consisting of $n$ (distinct) positive integers such that the average of any subset of $A$ is a square? (Feel free to replace "square" with "cube", "fourth power", ...
1
vote
2answers
59 views

The equation $5^x+2=17^y$ doesn't have solutions in $\mathbb{N}$

Problem: Prove that the equation $5^x+2=17^y$ doesn't have any solutions with $x,y$ in $\mathbb{N}$. I've been analyzing the remainder while dividing by $4$, but I'm getting nowhere.
0
votes
0answers
55 views

Pillai equation solvability

I would like to learn an elementary method of solving Pillai equation. The equation $a^x-b^y = c$ has at most two solutions for $(x, y)$ in $\mathbb{Z} $, where $a$ and $b$ are greater than or equal ...
1
vote
2answers
52 views

Is $a^{p^n-1}=1\mod p$ where $p$ is prime number and $1<a<p-1$?

Is $a^{p^n-1}=1\mod p$ where $p$ is prime number and $1\lt a\lt p-1$? When $n=1$ by little fermats theorem theorem it is true. But i can't justify generaly whether it is correct or not. But when i ...
4
votes
5answers
126 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c,$$ show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but ...
0
votes
1answer
32 views

Implications of a prime square dividing a binary quadratic form

Let $u,v$ be positive integers with $\gcd(u,v)=1$, let $k\ge 3$ be an odd integer, and fix a prime $p$. Now what are the implications of $p^2 \mid (u^2+kv^2)$? I know implications in certain cases, ...
1
vote
4answers
134 views

How to find the last non-zero digit of $50!$

A week ago i made a similar question but nobody help me, i´ve been trying but i still don't get it. I want to know how to find the last non-zero digit of $50!$. my try: First i have to know how ...
0
votes
2answers
57 views

Complete this reasoning? Number theory

I have this really weird confusion with $gcds$ and and basic theory dividing numbers and at the moment, I am stuck at this. If $gcd(a,b) = 1$, it means the biggest number that divides them evenly ...
0
votes
1answer
252 views

if ca ≡ cb mod n and d = (c,n) where n = dm . prove that a ≡ b mod m

if $ca \equiv cb \ (\textrm{mod}\ n)$ and d = (c,n) where n = dm , prove that $a \equiv b \ (\textrm{mod}\ m)$ so here is my attempt from $ca \equiv cb \ (\textrm{mod}\ n)$ we know that n | ca - ...
3
votes
2answers
1k views

Prove by contradiction that $\forall x,y \in \Bbb Z: x^2-4y \ne 2$

Prove that for all $x,y \in \mathbb{Z}$, $x^2 - 4y \ne 2$. Using a contradictory method would be appropriate. So, for this question, I assume, for the sake of a contradiction, that There exists ...
0
votes
2answers
236 views

A New, Possible Proof of the Infinitude of the Primes?

$$1=1$$ $$2=2$$ $$3=3$$ $4=2\cdot2$ At $4$, the first prime number, $2$, is there as a factor. So I say that at the square of $2$, $2$ comes into play as a prime factor. At this point, $2$ is the ...
3
votes
1answer
45 views

Bibinomial coefficient integer

For integers $n \ge k \ge 0$ we define the bibinomial coefficient. $\left( \binom{n}{k} \right)$ by $$ \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!} .$$ What are all pairs $(n,k)$ of integers ...
2
votes
2answers
133 views

Proof that $\sqrt{4}\notin\mathbb{Q}$ of course wrong but where is the flaw?

Assume $$\eqalign{ \sqrt{4}\in\mathbb{Q}&\Longrightarrow(\exists a,b\in\mathbb{Z})\sqrt{4}=\frac{a}{b}\text{ and }\gcd(a,b)=1\\ &\Longrightarrow 4b^2=a^2\Longrightarrow a\text{ is even}\\ ...
3
votes
0answers
121 views

finding all integers for which 23 is a quadratic residue

Some time ago I have solved an exercise and now, re-reading it, I don't understand a step. I ask your help in that. I will take some results for granted, although in the original exercise they were ...
1
vote
3answers
64 views

Are there any nonzero integers $a$ , $b$ such that $a^2$ = $3b^2$

I know since 3 is prime then nothing divides 3 except 3 and also 3 is a factor for only multiples of 3. $a^2$ must be a multiple of 3. But I am kinda stuck here.
0
votes
1answer
63 views

If a number is divisible by two others, then it's divisible by their lcm

Prove that if $c$ is a common multiple of $a$ and $b$, then $c$ is a multiple of $\operatorname{lcm}(a,b)$ Nobody in my class has found a way to do it. Whatever I try, I always come to the ...
2
votes
1answer
54 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for ...
0
votes
2answers
136 views

Is this true about the open intervals on the real line?

Let $a<b$ and let $m$ be a positive integer such that $$3^{-m} < \frac{b-a}{6}.$$ Then can we find a positive integer $k$ such that the open interval $$\left(\frac{3k+1}{3^m}, ...
5
votes
2answers
294 views

Discriminant of monic cubic function and integer roots

We all know that if the discriminant of a monic quadratic is a perfect square, then both of its roots will be integers. In my research, I'm interested in monic cubics, and I was wondering whether ...
0
votes
1answer
23 views

Finite Arithmetic Progressions - Beginning and End Points

First, I want to express the integers 27,29,31,33, and 35 in the form of a finite arithmetic progression. Second, I want to express the integers 37,39,41,43,45, and 47 in the form of a finite ...
1
vote
2answers
87 views

proportion of primes in a polynomial sequence

It is conjectured (Bunyakovsky) that when $P(x)$ is a polynomial from $\mathbb{Z}[X]$, irreducible, with positive leading coefficient and so that the integers $P(n)$ , $n\gt0$ do not share a common ...
2
votes
2answers
82 views

$n$ positive integer, then $n=\sum_{d|n} \phi(d)$ (proof Rotman's textbook)

I've just read in Rotman's group theory textbook the proof of the following statement: Statement If $n$ is a positive integer, then $$n=\sum_{d|n} \phi(d),$$ where the sum is over all divisors $d$ ...
0
votes
1answer
26 views

Proof of simple divisibility fact

If I want to prove that $a \nmid bc$, and I know that $gcd(a, b) = 1$, then why does it precisely does it suffice to show that $a \nmid c$? Thanks.
1
vote
2answers
23 views

Precise definition of congruence class?

So I'm going through Niven's The Theory of Numbers, and it gives the definition that: $$a \equiv b \pmod m \implies m \mid (a - b)$$ However, a few pages after this definition, it gives a theorem ...
2
votes
1answer
118 views

Are all transcendental numbers theoretically accessible?

I apologize if the title (and the body) of this question is worded incorrectly, but I have no real experience in (transcendental) number theory, so it's probably the best I can do. I've been thinking ...
2
votes
2answers
184 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...