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

learn more… | top users | synonyms (1)

0
votes
2answers
25 views

Can you show that $3n+1$ is not divisible by $5$ using congruences?

I'm trying to prove that the difference of two consecutive cubes is never divisible by $5$, and I got to a point where I would have to prove that $3n+1$ is not divisible by $5$, where n is an integer. ...
2
votes
1answer
27 views

Looking for a simpler solution about quadratic congruence

Here is the Problem: 1)Suppose $p$ is a prime. prove that for any integer $k$, there exist integers $x$ and $y$ such that $x^2+y^2 \equiv k\ \pmod p$. 2)Are there infinitely many composite ...
0
votes
3answers
52 views

Alternative Proof: if $n$ is an integer, prove that $\frac{n ( n^4 - 1)}{5}$ is an integer

I have proven this by the induction method but would like to know if it can be proven using an alternative method.
1
vote
0answers
21 views

Are there infinitely many primes such that… [duplicate]

Are there infinitely many primes $p$, such that, $p-1=n^2$ where $n\in \mathbb{N}$. As $p$ must be $odd$, we can say that $p$ must be of the form $4k+1$. But I do not know how to proceed.
0
votes
3answers
22 views

Prove that there exists no prime

If $\phi(n)\mid(n-1)$, then prove that there exists no prime $p$ such that $p^2\mid n$. This means that $n$ must be a product of different primes. But how do I prove that?
0
votes
0answers
16 views

For how many n's less than 100 do we have $s(n)=s(n+i)$

We define $s(n)$ as $LCM(least\ common\ multiplier)$ of numbers $1\ through\ n$. For how many $n's $ less than $100$ do we have: $s(n)=s(n+i),(i$ is a positive integer less than $10)??$ I have ...
1
vote
2answers
44 views

Partition of natural number not equal to factorial

I wish to prove the following statement so I can use it as a lemma for a group theory result. To be honest I have not tried much yet, my intuition tells me this is going to be connected to the ...
0
votes
1answer
9 views

On the relationship between $\max(p_i)$ and $\omega(b)$, if $\sigma(b^2)/b^2$ is bounded above by a specific number $U$

Let $\omega(x)$ denote the number of distinct prime factors of $x$, and let $\sigma(x)$ be the sum of the divisors of $x$. Denote the abundancy index of $x$ by $I(x) = \sigma(x)/x$. Let the number ...
1
vote
2answers
25 views

Charmichael number square free

Show that if $n$ is a Charmichael number, then $n$ is a square-free. I did this: Let $n= (p^t)(m)$ where $t >1$. Then by modular property, $$b^p= b \mod n , \,\, b^m= b \mod n$$ Above two ...
1
vote
1answer
11 views

Question about the validity of a proof involving the abundancy index

Let $\sigma(x)$ be the sum of divisors of $x$, and denote the abundancy index of $x$ by $I(x) = \sigma(x)/x$. Consider the number $y^2 \in \mathbb{N}$, and suppose that I know that $I(y^2) < 4/3$. ...
2
votes
2answers
46 views

Finding the sum of all products of pairs of distinct primitive roots mod 83

I'm currently studying Number Theory and I've stumbled upon a question where I need to: Find the sum of all products of pairs of distinct primitive roots mod 83. Solving attempt: I've tried to find ...
0
votes
2answers
33 views

Find $n$ such that the congruence $x^n\equiv 2\mod 13$ has a solution for $x$.

Find $n$ such that the congruence $x^n\equiv 2\mod 13$ has a solution for $x$. I am not getting any idea how to start this problem. Please give some hits
1
vote
0answers
31 views

$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$ integer for $k \in \mathbb{N}$

How do I see that for any positive integer $k$,$$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$$is an integer?
3
votes
1answer
40 views

How can I find the $n^{th}$ 'reversible prime'?

I just thought of an interesting problem when discussing prime numbers with a friend. Some numbers are prime, but even fewer numbers preserve their primality when we reverse their digits. So for ...
0
votes
0answers
12 views

Finding the fundamental Pell solution from a system of Pell-like equations

Assume $d$ is a non-square integer, and $r,s,t,w$ are integers, and $n$ and $m $ are integers with $n,m \neq 0,\pm 1$, satisfying the system of Pell-like equations \begin{align} r^2-ds^2 &= m, \\ ...
2
votes
1answer
30 views

Is it always true, for a prime $p$, a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$?

Let $p$ be a prime, then is it true that a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$? And if yes why?
-1
votes
0answers
32 views

Faster method to find sum (product) parts

I have a sum (product) that includes some specific values and I need to find how many values make that product. For example: I have $481$ and values$: 5, 29, 149$. I can find that $481 = 5 + 29 + ...
2
votes
3answers
101 views

Integer solutions to $x^2-xy+y^2=1$

What are the integer solutions to $x^2-xy+y^2=1$? (I found the solution below while working on another problem, so I thought I'll add it to the knowledge base here.)
6
votes
3answers
116 views

My formula for sum of consecutive squares series?

I stumbled upon a specific series, who's Sum of squares of consecutive integers equals the sum of squares of the continuation of that consecutive integers. For exmaple, this first number in the ...
-2
votes
0answers
39 views

Prime number theory. [on hold]

If $a$ is coprime to $b$ and $y$ and $b$ are both coprime to $x$; then Prove that $ax+by$ is a coprime to $ab$.
-1
votes
1answer
44 views

Conjecture: Partitioning $\Bbb N$ into parts that sum to $13^i$ [on hold]

Recently I was thinking and came up with a conjecture that goes as follows: Conjecture: There exists a $\Omega$ such that $$\Omega = \Bigg\{A_i \ \Bigg| \ \forall i,j:i\not=j, \ A_i\cap ...
0
votes
1answer
33 views

There exists an irrational number z such that x<z<y

I know there are lots of post about this but I wanted to know this proof would work also. Proposition. Let $x,y ∈ \mathbb{R}$ with $x < y$. There exists an irrational number $z$ such that $x < ...
1
vote
0answers
28 views

The Divisors of $s(2s+1)$ and Primes $n$, $4n+1$, and $6n+1$

This question is somewhat related to this one. Most of this is by way of a computer search: claim: If $s$ is any positive integer I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be the divisor ...
3
votes
3answers
55 views

Let $A = (0,1]$. Then$\text{ inf}(A) = 0$

I posted before about this proposition and I thought I got it right but then I was told that it is still wrong so I am really confused again.. Here is my proof Proof : Let $A = (0,1]$ Here, since ...
3
votes
1answer
27 views

How to prove that if the sum of the totatives of two numbers is equal then the numbers are equal?

As the title says, I am trying to prove that if the sum of the totatives of $a$ equals the sum of the totatives of $b$ then $a = b$ but I am stuck. I have that sum of totatives of $n = f(n)= ...
2
votes
1answer
34 views

Solving $(ap)^2-d(bq)^2=1$ for distinct primes $p,q$

I'm pondering the following claim regarding special cases of the Pell equation. Conjecture: For every pair of distinct primes $p$ and $q$, there exist integers $a$ and $b$, and a non-square integer ...
1
vote
2answers
21 views

Proving that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\ (mod\ p)$

How can I prove that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\pmod p$?
1
vote
2answers
40 views

Number of integral solutions for an equation

How do we approach this kind of problem of finding number of positive integral solutions to $$\frac{1}{x}+\frac{1}{y} = \frac{1}{n!}$$ Here $n$ is given.
0
votes
0answers
29 views

If $k(a^2+mb^2) = c^2+md^2$, what can be said about the form of $k$?

Let $k,a,b,c,$ and $d$ be integers, and let $m \ge 2$ be a non-square integer, such that $$ k(a^2+mb^2) = c^2+md^2. $$ QUESTIONS: What can be said about the form of $k$ with no further ...
1
vote
0answers
21 views

Number of integral solutions of $x_1.x_2.x_3=x$

Let $x$ be the element of the set $A=\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$ and $x_1, x_2, x_3$ be positive integers and $d$ be number of integral solutions of $x_1.x_2.x_3=x$ , then $d$ is ...
6
votes
1answer
99 views

Does rationality of $\cosh(nx)$ and $\cosh((n+1)x)$ imply rationality of $\cosh(x)$?

Suppose that $x\in\mathbb{R}^+$ and $n\in \mathbb{N}$. If $\cosh(nx)$ and $\cosh((n+1)x)$ are rational, can we show that $\cosh(x)$ is rational too? I guess the following equalities should be useful: ...
0
votes
0answers
45 views

If $\gcd(a,b) = \gcd(c,d) = 1$ and $ab = cd$, then $a=c$ and $b=d$. [on hold]

Is this conjecture true? If yes, can somebody help me prove it? If not, can anyone come up with a counter example?
1
vote
1answer
43 views

Can the cardinality of a strictly ordered set exceed the cardinality of the natural numbers?

I'm putting some thought into the CH at the moment and a proof of the answer to this question would be most helpful if anybody would be so kind as to help me out: Can the cardinality of a strictly ...
-1
votes
3answers
26 views

$5x \pmod 7 \equiv 6 \ $ then $\ x \pmod 7 \equiv \ ?$ [on hold]

As the question states, if $5x \pmod 7 \equiv 6$ then $x \pmod 7 \equiv $ what? I am not sure how to solve questions of this nature. If you could outline this example so I know how to solve ...
0
votes
0answers
27 views

Z is a subset of Q (the set of all rational numbers)

Let $$n \in Z$$ Then $$n*1=n$$ and so $$n=n/1$$ Note n and 1 are both in Z. so n can be written in the form of $$ z = m/n,\,\,\, where\,\, m,n \in Z\,\,\,and\,\,\, n ≠ 0$$so $$n\in Q$$ Is it enough ...
0
votes
1answer
25 views

Logic Integer Proof with Common Divisors

Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ ...
1
vote
1answer
55 views

Find all the solutions of the congruence $12^x \equiv 17 \bmod 25$

I need to find all the solutions of the congruence $12^x \equiv 17 \bmod 25$. I don't really have an idea how to approach this.. I tried to write it as: $12^x \equiv 17 \mod 25$ ...
1
vote
3answers
50 views

Rational number proposition

**Prop.**Every $$r \in Q$$ can be written as r = m/n, where $$ m,n \in Z$$ such that n>0 and gcd(m,n) = 1 (r is in lowest terms) If I start by saying that let $$r \in Q$$ Then there exist $$a,b \in ...
1
vote
3answers
26 views

Simple-to-play morra game to select m winners from n contestants.

I have m apples and n people (m < n) and we need to play a fair deterministic game to decide who gets the apples. I know how to do this if m is 1 with morra, having each player submit an integer ...
2
votes
1answer
22 views

Classification of moduli where relatively prime numbers squared are 1

I came across an interesting property of certain numbers with respect to modular arithmetic and I was wondering if anybody had any more information about them. Consider an integer $n$ such that if ...
3
votes
3answers
49 views

Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

I need to find all the solutions of the congruence $x^2 \equiv 9 \mod 256$. I tried (apparently naively) to do this: $x^2 \equiv 9 \mod 256$ $\Leftrightarrow$ $x^2 -9 \equiv 0 \mod 256$ ...
4
votes
1answer
93 views

How many divisors does $111…1$ have?

Let $A=\underbrace{11..1}_{2010}$. How many divisors does $111...1$ have? Original problem: Prove that $τ(A)>50$ (or $τ(A)<50$) My work so far: If $\tau(A) -$ the number of divisors ...
2
votes
1answer
72 views

A seemingly-trivial divisibility conjecture

While working on another problem, I stumbled on the following divisibility claim. Conjecture: No integers $a,b,c,d$ satisfy all of the following conditions: $a^2+b^2-c^2-d^2 = 2(ad-bc)-1$; ...
1
vote
1answer
18 views

If $\sigma(N)$ is odd, $N = 2y^2$, and $y$ is not a power of two, does it follow that $\gcd(2,y) = 1$?

Let $\sigma(N)$ denote the sum of the divisors of the number $N$. It is well-known that $$\sigma(N) \equiv 1 \pmod 2 \iff \left\{\{N = x^2\} \lor \{N = 2y^2\}\right\}.$$ Here is my question: If ...
2
votes
1answer
26 views

How to find a square root mod $pq$ given that $p \equiv q \equiv 3 \pmod 4$

Let $n = pq$ where $p$ and $q$ are prime. We do not know $p$ and $q$. All we know is that $p \equiv q \equiv 3 \pmod 4$. From this we need to find a number $y$, in terms of $n$ and $x$, such that $y^2 ...
0
votes
1answer
18 views

Understanding a proof from Rotman's “Advanced Modern Algebra”(Chinese Remainder Theorem)

Please, read this post. I don't need to find any proof of the theorem, a I need to understand a specific step in a stecific proof. This is the proof from J.Rotman's book "Advanced Modern Algebra" 3rd ...
5
votes
4answers
58 views

Total number of integers relatively prime to $p^2$

I am reading my number theory textbook and it states without proof that the total number of elements relatively prime to $p^2$ for some prime $p$ is $p(p-1)$. Why is this so? I know that the number of ...
5
votes
2answers
47 views

Rational Question for $a + b$ and Irrationality of $a^2 + b^2$

I have looked into the question and need help. Find some $a,b$ ${\in}$ $\mathbb{R}$ such that $a + b$ ${\in}$ $\mathbb{Q}$, $a^2 + b^2 \not\in \mathbb{Q}$, and $\frac{a}{2} < b < a$. Or prove ...
1
vote
1answer
46 views

I get a wrong answer for the gcd of two polynomials

Hello first post here, I am trying to get the gcd of the two polynomials using the euclidean algorithm, but as result I get a fraction with huge numbers, instead of 1, which I get as result after ...
0
votes
1answer
24 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...