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

learn more… | top users | synonyms

1
vote
0answers
34 views

Calling all genius: $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 integer $e_i$ and prime number $p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}$ for $k\ge 1$. Is this impossible or what? I've been trying for at least a week. I've ...
1
vote
1answer
20 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
30 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 ...
6
votes
1answer
104 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
15 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: ...
0
votes
1answer
32 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 ...
2
votes
0answers
33 views

Numbers represented as two different sums of squares

This is an interesting question I came across, and it looks not that easy! $365$ can be written as a sum of $2$ consecutive perfect squares and also $3$ consecutive perfect squares: $$ \large ...
0
votes
2answers
38 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
19 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
1
vote
0answers
28 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 ...
3
votes
2answers
32 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
18 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
50 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 ...
1
vote
1answer
20 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
39 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
24 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", ...
0
votes
0answers
10 views

Solving $-\alpha x^2-\beta y^2-\alpha\beta z^2=-p$ to check for isomorphism of quaternion algebras.

Edited I am considering quaternion algebras $(-\alpha,-\beta)_\mathbb Q$, with $\alpha,\beta>0$. I am trying to find several of these, which are not isomorphic. I do not want to digress into ...
1
vote
2answers
47 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
17 views

Pseudorandom Noise Sequences

A PN sequence based on LFSR can be analyzed using the Berlekamp-Massey algorithm. If I have a sequence that is a combination of two LFSR sequences, is there a similar way to recover the two LFSR ...
0
votes
0answers
26 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 ...
3
votes
5answers
83 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 I ...
0
votes
1answer
21 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
3answers
53 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
45 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
0answers
21 views

Reducing a sum of four squares to a sum with root sum equal to $1$

It is well-known that every odd natural number can be written as the sum of four squares. Perhaps less well-known is the fact that every odd natural number can be written as the sum of the squares of ...
0
votes
1answer
16 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 - ...
0
votes
2answers
137 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
36 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
82 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}\\ ...
2
votes
0answers
28 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 ...
0
votes
1answer
39 views

Use Fermat’s Little Theorem to show that if $p = 4n + 3$ is prime, there is no solution to the equation $x^2 \equiv −1 \pmod p$. [on hold]

Use Fermat’s Little Theorem to show that if $p = 4n + 3$ is prime, there is no solution to the equation $x^2 \equiv −1 \pmod p$. Can someone please explain it step by step
1
vote
3answers
52 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.
2
votes
1answer
42 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 ...
1
vote
2answers
123 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}, ...
3
votes
2answers
24 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
15 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
55 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 ...
1
vote
2answers
37 views

$n$ positive integer, then $n=\sum_{d|n} \phi(n)$ (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(n),$$ where the sum is over all divisors $d$ ...
32
votes
0answers
3k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
0
votes
1answer
20 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.
0
votes
2answers
14 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 ...
1
vote
1answer
55 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 ...
1
vote
2answers
77 views

Show that there exists no integer b such that f(b) is 1993.

We are given a polynomial $f$ with integer coefficients such that for 4 distinct integers $a_1,a_2,a_3$ and $ a_4$, $f(a_1)=f(a_2)=f(a_3)=f(a_4)=1991$. Show that there exists no integer $b$ such that ...
0
votes
1answer
25 views

Maximum and Minimum in Set Theory

In a group of 100 students, each student has to opt for one or more of the three subjects among Physics, Chemistry and Mathematics. The number of students who opted for Mathematics is more than the ...
1
vote
1answer
81 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
1
vote
1answer
48 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
6
votes
2answers
106 views

Prove that $2^n +1$ in never a perfect cube

Prove that $2^n +1$ in never a perfect cube I've been thinking about this problem, but I don't know how to do it. I know that if $m^3=2^n+1$, then $m$ should be an odd number, but I 'm not able to ...
2
votes
0answers
48 views

Is Legendre’s solution of the general quadratic equation the only one?

Legendre famously solved the general quadratic equation $$ ax^2+bxy+cy^2+dx+ey+f=0 $$ by noting that \begin{equation*} 4a(b^2-4ac)(ax^2+bxy+cy^2+dx+ey+f) = 0 \tag{$\star$} \end{equation*} along with ...
0
votes
3answers
41 views

Whether the given number is divisible by 24?

Let $a$ be an integer which is not divisible by 2 and 3. Prove that 24 divides $a^2-1$. This, $a$ can be written as $a=2x+1$ or $a=3z+r$ where $r=1,2$ and $x$ and $z$ are integers. This $a^2-1= ...
1
vote
3answers
83 views

Non-linear diophantine equation

Let $k$ and $n$ be positive integers and $y(n-x)=(k+nx)$. What is the condition of $k$ and $n$ such that there exist positive integers $x, y$ as the solution of $y(n-x)=(k+nx)$?