Question

How to find Automorphic numbers/Circular numbers?

Answer 1

@phi ?

Answer 2

sorry, engineers don't study that stuff.

Answer 3

Okay. :)

@mathstudent55 ?

Answer 4

@ganeshie8 ?

Answer 5

definition :
if \(a\) is an \(n\) digit automorphic number, then :
\(a^2\) leaves a remainder \(a\), when divided by \(10^{n}\)

Answer 6

u wanto generate these using some program... or wanto derive some formula analytically ? wat exactly u looking for ha ? :)

Answer 7

I am looking to derive it analytically!
For eg.

25^2 = 625

I found a way to derive this. [For 2 digit numbers]

(10x + 5)^2 = 100y + 10x + 5

100x2 + 100x + 25 = 100y + 10x + 5

100x2 + 90x + 20 = 100y

10x2 + 9x + 2 = 10y

10x2 + 5x + 4x + 2 = 10y

(5x+2)(2x+1) = 10.y = 2.5y = 5.2y

(5x+2)(2x+1) = 2y.5

2x+1 = 5
x = 2

5x+2 = 2y
5(2) +2 = 2y

y = 6.

Thus

(10x+5)^2 = 100y+10x+5 => 25^2 = 625

I wanted a method similar to this to find all the Automorphic numbers.

Is it possible?

Answer 8

let me comprehend ur method
fyi : i heard automorphic number for the first time, today

Answer 9

Sure! Okay. Same here. :P

Answer 10

meantime let me tag few who took number theory before : @ikram002p @mukushla @Jonask @UnkleRhaukus @kc_kennylau @oldrin.bataku

Answer 11

and @atlas :)

Answer 12

Thanks!

Answer 13

to find all \(n\) digit automorphic numbers, we solve below :

\(\large x^2 \equiv x \mod 10^n \)

Answer 14

u familiar wid cogruences ?

Answer 15

No. Can you explain? Or can you, post some web links which explain the concept with much fluidity?

Answer 16

sure, when u r back we can go thru in detailed :)
it involves basic remainder arithmetic.

Definition :
\(\large a \equiv b \mod n \)

means,

\(\large a-b\) is divisible by \(\large n\)

Answer 17

few examples :
\(\large 12 \equiv 2 \mod 10 \) cuz, \(12-2\) is divisible \(10\)

\(\large 7 \equiv -3 \mod 10 \) cuz, \(7--3\) is divisible \(10\)

\(\large 1 \equiv 4 \mod 3 \) cuz, \(1--4\) is divisible \(3\)

Answer 18

i haven't taken number theory @ganeshie8

Answer 19

In laymen terms, an automorphic number is a number whose square ends with the number. e.g. 25->625

Answer 20

\[\large x^2-x=a*10^{\lceil \log x\rceil}\]

Answer 21

Is there any way to understand that formula? @kc_kennylau

Answer 22

I don't think the formula I've provided is the solution, but \(\lceil\log x\rceil\) is the number of digits \(x\) has.

Answer 23

This is one more solution I found online!

http://www.mathsisfun.com/puzzles/four-digit-whole-number-solution.html

Answer 24

Can you guys explain the logic used in that link's solution?

Answer 25

The link's solution is a trial-and-error solution.

Answer 26

0->0, 1->1, 2->4, 3->9, 4->6, 5->5, 6->6, 7->9, 8->4, 9->1

Answer 27

Yeah!

That would mean we would have to try 10 times for every power of 10!

I guess I'll learn congruences and then try applying that formula.

Answer 28

square of any number can oly hav last digit as one of : 1, 4, 5, 6, 9

Answer 29

yeah that wud be a good idea, but it will take time to learn congruences...

just nitpicking :
\(x^2 \equiv x \mod 10^n\) is not a formula, it is just a relation expressing the problem at hand :)

solving that relation requires knowledge of congruences theory

Answer 30

I have a deadline of 12th March. I'll try to do something about it. Thanks! :D

Answer 31

good luck ! and dont work it alone... share wid us ur progress :)

Answer 32

Sure! Thanks man! (y)

Answer 33

I can't provide a formal solution as this is the first time I heard about "Automorphic numbers" and "Congruency Theory" . Here's whatever I can comprehend.

By the Vedic Sutra "Urdhva-tiryagbhyam" ; it is obvious that for AB = C
last 'n' digits of C depends only on the last 'n' digits of A and B

Hence, among single digit numbers;
\[x^2 ≡ x \mod10\]
\[x \in \left\{ 1,5,6 \right\}\]

For double digit numbers (we only need to check for those ending with 1, 5, 6)
Those ending with 1
\[2x≡x \mod 10\]
\[x \epsilon \phi\]
(Note that x can't be zero)

Those ending with 5
\[10x+2≡x \mod 10\]
\[2≡x \mod 10\]
\[x \epsilon \left\{ 2 \right\}\]

Those ending with 6
\[12x+3≡x \mod 10\]
\[2x+3≡x \mod 10\]
IDK how to solve that, so - http://www.wolframalpha.com/input/?i=2x%2B3%E2%89%A1x+mod+10
\[x \epsilon \left\{ 7 \right\}\]

Hence, double digit automorphic numbers are 25 and 76.

Similarly, for triple digit numbers we have to check for those ending with 25 and 76

Answer 34

In general, to find 'n' digit automorphic number (when 'n-1' digit automorphic numbers are known)

\[\left( 2a_na_1+2a_{n-1}a_2+... \right)+y≡a_n \mod 10\]
where the subscript denotes the place value of the digit
y = ('n-1' digit automorphic number)^2 - ('n-1' digit automorphic number)

Hence, the only unknown would be
\[a_n\]

@ganeshie8 Can such an equation be solved by congruency theory ??

Answer 35

PS: For three digit numbers, we also have to check for those ending with 01, 05, 06
Although, it will lead to
\[2x≡x \mod10\]
\[x \epsilon \phi\]

In other words, we can say that there cannot be a 3 (or more) digit automorphic number ending with 01, 05, 06

But don't take such cases for granted. For e.g. 90625 is an automorphic number.

Answer 36

Thanks @lastdaywork I tried understanding that, but failed. I suppose, as @ganeshie8 had told me, I'd better learn congruences before I doing this question. :)

Answer 37

You're welcome :)