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

learn more… | top users | synonyms (1)

0
votes
0answers
37 views

Rational And Real Numbers Density

I know that $\mathbb{Q}$ and $\mathbb{R}$ are dense and that there cardinalities are $\aleph_0$ and $\aleph$ corresponding. Does from these facts I can assume that any interval of $\mathbb{Q}$ or ...
1
vote
0answers
30 views

Diophantine linear Equation Gaussian Integers

We know that $ax+by=c$ with $gcd(a,b)=1$ could be solved over $\Bbb Z$. Supposing if $a,b,c\in\Bbb Z[i]$, is there an analogous framework to find $x,y\in\Bbb Z[i]$ (at least of minimum norms)?
0
votes
1answer
98 views

On a theorem of Kronecker! [closed]

Let $\alpha$ be an irrational number and $\beta$ be an arbitrary real number, Prove that there are infinitely many pair of integers $(x,y)$ with $x\in\mathbb{N}$ such that: ...
0
votes
1answer
62 views

all elements of ($Z$/p$Z$)* are cubes

Let $p$ be a prime An element $a \in$ ($Z$/p$Z$)* is called a cube if there exists $b \in$ ($Z$/p$Z$)* such that $a = b^3$ How to show that all elements of ($Z$/p$Z$)* are cubes ? And if $p \equiv ...
1
vote
1answer
50 views

Find the sum of the digits of the number

Obviously, $a_1 \ne 0$ and $a_1 \ge 1$. $$N = 10^n a_1 + 10^{n-1} a_2 + \cdots + 10^0 a_n$$ But I dont think I can do a lot more.
6
votes
2answers
52 views

The product of all differences of the possible couples of six given positive integers is divisible by 960.

How can I show that the the product of all differences of the possible couples of six given positive integers is divisible by $960$? $$x_1≥x_2≥x_3≥x_4≥x_5≥x_6$$ $$960\mid (x_1-x_2 )(x_1-x_3 ...
5
votes
1answer
116 views

Denesting a square root: $\sqrt{7 + \sqrt{14}}$

Write: $$\sqrt{7 + \sqrt{14}} = a + b\sqrt{c}$$ Form. $$7 + \sqrt{14} = a^2 + 2ab\sqrt{c} + b^2c$$ $a^2 + b^2c = 7$ and $2ab = 1$, and $c = 14$ But that doesnt seem right as $a, b,$ wont be ...
-1
votes
2answers
63 views

If p is an odd prime then prime divisors of $(2^p-1)$ [duplicate]

If $p$ is an odd prime Prove that the prime divisors of $(2^p-1)$ are of the form $(2rp+1)$.
0
votes
1answer
31 views

Show that $29 | N$ Problem

Let $\frac{29}{25} x_1$ and $\frac{39}{50}x_2$ equal $N$ for some $x_1,x_2$. If $x_{1,2}$ are positive integers show that: $$29 | N,\space \text{and} \space 39 | N$$ So, $$29 | N \implies ...
2
votes
2answers
139 views

$a, b \in\Bbb N$, find all solutions to $2^a = b^2 - 5$ and prove there are no more solutions?

I am currently studying discrete mathematics at uni (in my computer science degree). We have an assignment due tomorrow, and i have been able to do most of it, but one question eludes me. I spoke to a ...
1
vote
2answers
65 views

Form of a prime dividing a certain difference of two prime powers.

Let $p$ and $q$ be odd primes. If $q|(a^p-1)$ then, either $q|(a-1)$ or $q=(2rp+1)$ for some integer $r$.
2
votes
3answers
55 views

Given LCM of three natural numbers, find the possibilities.

LCM of three natural numbers =150. How many sets of three numbers are possible? I know how to do this for two natural numbers.There is also a general formula for that. But for 3 numbers it is posing ...
5
votes
1answer
68 views

Smallest number of primes

Let $P$ be a set of primes, such that for each nonnegative integer $n$, $19⋅8^n+17$ is divisible by some prime $p$ in $P$. Find the smallest possible number of elements in $P$. How do I start the ...
1
vote
0answers
34 views

Let $f(x), g(x) \in C[x]$. Suppose $f(x) | g(x)$ and let $c \in C$. Prove that if $f(c) = 0$ then $g(c) = 0$. Is the converse true?

Let $f(x), g(x) \in C[x]$. Suppose $f(x) | g(x)$ and let $c \in C$. Prove that if $f(c) = 0$ then $g(c) = 0$. Is the converse true? What I have so far: Since $f(x) | g(x)$, $f(x) = g(x)q(x)$ from ...
1
vote
2answers
65 views

From any ten naturals, find some numbers whose sum is divisible by $ 10.$

Consider $A \subset \mathbb N $ such that $|A| = 10.$ Then prove that there exists a non-empty $B \subseteq A$ such that the sum of the elements in $B$ is divisible by $10.$ How to go to the gist ...
0
votes
1answer
49 views

Product of Distinct Primitive roots

Let $p$ be an odd prime. Show that the product of the distinct primitive roots, $\mod{p}$, is $\equiv$ $1$ or $-1$ $\pmod{p}$. I think this can be done by viewing the primitive roots as a elements of ...
0
votes
0answers
37 views

$n^3 + n^2 + n + 1 = m^2$ for positive integers $m$ and $n.$ [duplicate]

How do I prove that $n = 7, m = 20$ and $n = 1, m = 2$ are the only solutions to this? I don't think it can be proved that it always lies between $2$ squares for all numbers other than $1$ and $7.$
7
votes
2answers
152 views

Solve $x^3=y^2-y+1$ in positive integers.

I recently started doing number theory and have finished with all the basic, intermediate and some of the advanced stuff with ease. However, I encountered this question and have been stuck for about a ...
-1
votes
0answers
29 views

GCD and remainders

Can anyone please help me with a problem associated to GCD. Say we have 2 numbers 30 and 42. What is the largest integer which when divides these two numbers will produce the same remainder? The ...
3
votes
1answer
50 views

Prove that for all naturals $n \ge 6$ there is a set of $n$ positive naturals, $a_1$ to $a_n$ such that $\sum_{i=1}^n \left(\frac{1}{a_i}\right)^2 =1$

I don't know how to prove this. I know that $\{2, 2, 2, 2\}$ is a set for $n = 4$, since $\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + ...
1
vote
2answers
72 views

Prove if, $2^n - 1$ is prime, then $n$ is prime. [duplicate]

Prove, when $n$ is a positive integer, if $2^n - 1$ is prime, then $n$ is prime. I did read some sort of proving on the web, but I could not understand it... Any help? And if possible, could the ...
3
votes
1answer
23 views

In $\mathbb{Z}$, let m~n iff m-n is a multiple of 10.

Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with that equivalence relation. In $\mathbb{Z}$, let m~n iff m-n is a ...
2
votes
1answer
27 views

Proof that $a,r,s$ are odd and $b$ is even

I was trying to do this proof where: Assume $a,b,r,s$ are relatively prime, and that $$a^2+b^2=r^2$$ and $$a^2-b^2=s^2$$ Prove that $a,r,s$ are odd and $b$ is even. So I started off by saying that ...
0
votes
1answer
61 views

Is there a special term for an injection from A to B and a surjection from B to A.

I wish to know if there is a special term for an injection from A to B and a surjection from B to A. I have a set of systems of congruences using large prime numbers for the modulii that maps onto ...
1
vote
0answers
43 views

Let p and q be distinct prime numbers with p≡q≡3 mod 4. Prove that if

the congruence x^2≡p mod q is not solvable, then the congruence x^2≡q mod p has exactly two incongruent solutions modulo p. I'm not exactly sure where to start with this problem. Any help is ...
0
votes
3answers
29 views

Prove that gcd(e,f)=1

could someone please help me with this proof? Suppose that a, b ∈ N, and d = gcd(a, b). Since d divides a, we have a = de for some integer e, and similarly b = df for some integer f. Prove that ...
2
votes
1answer
43 views

Positive rational numbers $a$,$b$ satisfy $a^3+4a^2b=4a^2+b^4$. Prove that $\sqrt{\sqrt{a}-1}$ is also rational.

Positive rational numbers $a$,$b$ satisfy $a^3+4a^2b=4a^2+b^4$. Prove that $\sqrt{\sqrt{a}-1}$ is also rational. My try: $a(a+2b)^2=a^3+4a^2b+4b^2a=4a^2+b^4+4b^2a=(2a+b^2)^2$, so ...
2
votes
4answers
66 views

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction What I thought: Inductive hipothesis: $$ 5^{2n}+12n^2-36n-1=24k $$ Inductive step: $$ 5^{2(n+1)}+12(n+1)^2-36(n+1)-1=24q $$ $k,q \in \mathbb{Z}$ ...
3
votes
2answers
36 views

Number of elements of $\mathbb{Z}_p$ that satisfy a certain property

Let $S(n,p)=\{a\in \mathbb{Z}_p : a^n=1$ (mod $p$)$\}$ where $p\geq3$ is a prime number and $1\leq n\leq p$. I am interested in finding a general formula for cardinality of $S(n,p)$. For example, I ...
-4
votes
3answers
70 views

$n \equiv 1 \pmod{2m} \Rightarrow n \equiv 1 \pmod{m}$ but converse is false [closed]

Prove if $n \equiv 1 \mod 16$, then $n \equiv 1 \mod 8$ BUT if $n \equiv 1 \mod 8$ then it is not necessarily true that $n \equiv 1 \mod 16$. Prove that if $n \equiv 1 \mod 2m$, then $n \equiv 1 \mod ...
1
vote
1answer
53 views

Number System Conversion

0 down vote favorite I have a paradox: EIGHTY is a six digit number with no repeating digits and no zeros. When divided by 19, 17, 13, 11, or H, the remainders are, respectively, 17, 13, 11, 7 and G. ...
5
votes
1answer
49 views

An integer sequence with integer $k$ norms

Find the maximum value of $n$(if exists) such that there exists a sequence $a_1,a_2,\ldots,a_n$ of positive integers such that for every $2\leq k \leq n$ $$\sqrt[k]{a_1^k+a_2^k+\cdots+a_k^k}$$ is ...
0
votes
1answer
16 views

How many pickups $K$ should I do to have a $p$% of probability of picking up a divisor of $n$ (if exists) in the interval $[2..\lfloor n/2\rfloor]$?

I am trying to understand if it makes sense an algorithm to decide if a given number $n$ is possibly prime or not by using the divisor function bound defined by professor Jeffrey Lagarias as: ...
2
votes
2answers
53 views

Modular Congruence with prime factorization!

Show that if n is a natural number and n is congruent to 3 (mod 4) then one of the prime factors of n must also be congruent to 3 (mod 4) I honestly don't know where to begin with this problem. It ...
0
votes
1answer
16 views

Modular Congruence

I need to somehow use mod 2 and Modular congruence to prove whether or not the following number is even or odd: $722^{77}$-$333^{99}$($55^{100}$) What I was thinking about doing was evaluating as two ...
0
votes
2answers
59 views

Suppose that $n \in \mathbb{Z}$. Prove that if $n^2 + 1$ is a perfect square, then $n$ is even.

This is a homework problem that I cannot figure out. I have figured out that if $n^2 + 1$ is a perfect square it can be written as such: $n^2 + 1 = k^2$. and if $n$ is even it can be written as ...
2
votes
2answers
63 views

Sum of Fibonacci numbers

While trying to find find a formula to calculate the length of the golden spiral I came across the sum of the Fibonacci numbers. I noticed that $$\text{Fibonacci numbers: }1,1,2,3,5,8,13,21,34...$$ ...
7
votes
2answers
93 views

Find $p,q$ s.t. $2q^2-p^2=\Box$ and $2p^2-q^2=\Box$

Problem. Find all integers $p,q$ such that $2q^2-p^2$ and $2p^2-q^2$ are perfect squares. I think this is only true when $p=\pm q$ but I have not been able to prove it. One approach I tried is ...
1
vote
3answers
88 views

Prove that there is a multiple of 2009 that ends with the digits 000001

Prove that there is a multiple of 2009 that ends with the digits 000001. May one generalise this to: There exists a multiple of $x$ that ends with the digits $y$ (where $y$ consists of ...
0
votes
1answer
16 views

Deduce that the power of $p$ dividing $n!$ is $p^{e_p}$, where $e_p<\frac{n}{p-1}$

Question: Let $n\in\mathbb{N}$ and $p$ prime i) Show $\forall h\in\mathbb{N}$, the number of $m\in\mathbb{Z}$, with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$, ...
2
votes
2answers
63 views

Find all $n\in\mathbb{Z}^+$ such that the sum of the digits of $5^n$ equals $2^n$ [duplicate]

Find all $n\in\mathbb{Z}^+$ such that the sum of the digits of $5^n$ equals $2^n$ Starting with a table of values, I found that $n=3$ works. Beyond this, it's hard to imagine any other number ...
5
votes
2answers
258 views

Diophantine system of two equations with four variables

Find all integer solutions for the system: $$\left\{\begin{array}{rcl}xy + vw &=& 5 \\ xv - yw &=& 6\end{array}\right.$$ It's supposed to be solvable by 9-graders...
-6
votes
1answer
27 views

Almost-K-First-P-Prime [closed]

Almost-K-First-P-Prime A number is Almost-K-Prime if it has exactly K prime numbers (not necessarily distinct) in its prime factorization. For example, 12 = 2 * 2 * 3 is an Almost-3-Prime and 32 = 2 ...
0
votes
2answers
58 views

Multiplying two expressions containing perfect squares to get another perfect square

Is it possible to multiply a perfect square by the previous square plus one and get another perfect square? An example that doesn't work: $$6^2 (5^2 + 1) = 936 \ne n^2$$
1
vote
2answers
57 views

Let a,b,d belongs to natural numbers. If d divides ab then either d divides a or d divides b [closed]

Let $a,b,d$ belongs to natural numbers. If $d$ divides $ab$ then either $d$ divides $a$ or $d$ divides $b$. If true give proof , if false give counter example?
0
votes
1answer
43 views

Understanding a test for divisibility by 9

On page 32 of J.E Thompson’s Arithmetic for the practical man, he writes (emphasis added): Consider next divisibility by 9. Since 10=9+1, any number of 10’s equals the same number of 9’s plus the ...
3
votes
1answer
59 views

An infinite sum based on the mod-parity of Euler's totient function

Let $\bmod( m,k )$ be the remainder when $m$ is divided by $k$: $0,1,\ldots,m{-}1$. Let $\phi(n)$ be Euler's totient function: the number of relatively prime numbers smaller than $n$. So for ...
0
votes
1answer
43 views

Proof that minimum of sum of absolute differences is greater or equal of max value minus min value

Let's have an vector of natural numbers $[v_1, ..., v_N]$ my goal is to show that $$\sum_{i=1}^{N-1}|v_i - v_{i+1}| \ge v_{max} - v_{min}$$ where $v_{max} = \max_{i\in1...N}(v_i)$ and $v_{min} = ...
3
votes
1answer
45 views

Counting the number of integers $i$ such that $\sigma(i)$ is even.

Define $\sigma(i)$ to be the sum of all the divisors of $i$. For example, $σ(24) = 1+2+3+4+6+8+12+24 = 60$. Given an integer $n$, how can we count the number of integers $i$, less than or equal to ...
0
votes
1answer
19 views

formula for the number of perfect squares mod $N$

In a numerical experiment I notice for sum moduli $N$ there are much less than $N/2$ perfect squares. I had chosen a large number, the simplest example is $N=8$. Using the Chinese Remainder Theorem ...