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

learn more… | top users | synonyms (1)

2
votes
2answers
29 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
18 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$. ...
3
votes
2answers
152 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
35 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
2
votes
0answers
41 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?
4
votes
1answer
49 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 ...
1
vote
0answers
17 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
34 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
39 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
125 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
131 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 ...
-1
votes
1answer
45 views

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

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
34 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
30 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
68 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
30 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)= ...
3
votes
1answer
39 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 ...
2
votes
2answers
26 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
42 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.
2
votes
0answers
42 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
106 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: ...
1
vote
1answer
77 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
vote
1answer
50 views

$\mathbb{Z}$ is a subset of $\mathbb{Q}$ (the set of all rational numbers)

Let $$n \in \mathbb{Z}$$ Then $$n*1=n$$ and so $$n=n/1$$ Note $n$ and $1$ are both in $\mathbb{Z}$. so n can be written in the form of $$ z = m/n,\,\,\, \text{where}\,\, m,n \in ...
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
74 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
53 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
27 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
25 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
83 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
96 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
75 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
30 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
24 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
60 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
51 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
53 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
26 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 ...
2
votes
3answers
54 views

For $a,b>2$, $a,b\in \Bbb{N}$ , prove that $2^a+1$ is never divisible by $2^b-1$ [duplicate]

I have to prove that for $a,b>2$, $a,b\in \Bbb{N}$ that $2^a+1$ is never divisible by $2^b-1$. The method I used is by taking cases, first of them being $b>a$. Now since $b>a$ implies ...
0
votes
2answers
53 views

How do you split a fraction into a sum of fractions?

To add: $$\frac25+\frac37=\frac{14+15}{35}=\frac{29}{35}$$ But if asked to return $\frac{29}{35}$ to a sum of fractions how would one go about this? My attempt: ...
3
votes
2answers
50 views

The condition about some positive real numbers can be written as the sum the nearby two

Given $n$ positive real numbers $x_1,...,x_n$. What is the condition that they can be written as $$x_1=y_1+y_2$$ $$x_2=y_2+y_3$$ $$\ldots$$ $$x_n=y_n+y_1$$ where $y_1,\ldots,y_n$ are also some ...
1
vote
1answer
27 views

all pairs of a and b in an equation containing gcd

Find all pairs of positive integers $a,b$ such that $$ab=160+ 90\cdot \gcd(a,b)$$ how do we approach this type of problem in number theory or what is the best way to solve this ?Here gcd is greatest ...
0
votes
0answers
24 views

Prove one prime occurring to at least the t-th power

Prove that for all pairs of positive integers s and t, there are infinitely many sequences of s consecutive positive integers, each of which, when factored into prime powers, has at least one prime ...
8
votes
1answer
111 views

Can this puzzle be solved without brute force?

Consider positive integers $a$ and $b$, where $a \ge b$ and the sum $\frac{a+1}{b}+\frac{b+1}{a}$ is also an integer. Find the sum of all $a$ values less than $1000$ that meet this criteria. For ...
1
vote
2answers
46 views

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

I am having a problem with this statement. I am trying to prove that 0 is the greatest lower bound by showing that every lower bound greater than 0 is a contradiction but I can't figure our how. ...
0
votes
5answers
81 views

Proof that if $(n+1)^2 -1$ is even then $n$ is even?

The forward implication, if $n$ is even then $(n+1)^2 -1$ is even, was simple. I can't figure out the other implication: if $(n+1)^2 -1$ is even then $n$ is even. What type of proof do I want to ...
1
vote
5answers
53 views

Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. [duplicate]

Full question: Let $p$ be a prime and let $a$ be an integer such that $1 \leq a < p$. Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. Looking for the ...
3
votes
1answer
48 views

Factorising an integer in $\Bbb{Z}[\sqrt{-2}]$

So I just completed this exercise: My solution involved taking norms, deducing that $N(\alpha)=p$ for some $\alpha\in\Bbb{Z}[\sqrt{-2}]$ which is not a unit. Then supposing $$\alpha=a+b\sqrt{-2}$$ ...
0
votes
0answers
30 views

Question about the solutions to quadratic congruence $x^2\equiv -1(\mbox{mod}\;p)$

As is known to all, when $p\equiv 1(\mbox{mod}\; 4)$, there are 2 solutions to the congruence in the set $\{1,2,3,...p-1\}$: $$x^2\equiv-1(\mbox{mod}\;p)$$ which to be exact are ...