I am using Python 3.6.2 on Ubuntu 16.04. On all prior versions of Python, I have never had this issue. I have googled around. There is no post on AskUbuntu on this specific issue that I could find. There is one on SO, but it is pretty old. I don't have etc/pythonstart as the accepted answer suggests and this is the ONLY place I've found that even references such a thing.
This SO answer is also old, but when I tried the solution:
malikarumi@Tetuoan2:~$ apt-get libreadline-dev
E: Invalid operation libreadline-dev
malikarumi@Tetuoan2:~$ sudo apt-get libreadline-dev
[sudo] password for malikarumi:
E: Invalid operation libreadline-dev
malikarumi@Tetuoan2:~$ apt-get libreadline
E: Invalid operation libreadline
malikarumi@Tetuoan2:~$ sudo apt-get libreadline
E: Invalid operation libreadline
malikarumi@Tetuoan2:~$ apt-get readline
E: Invalid operation readline
malikarumi@Tetuoan2:~$ sudo apt-get readline
E: Invalid operation readline
I do have the GNU Readline Library, up to 6, in usr/share/doc, so I don't know why that's not working for me since, as I said, I never had this issue on <3.6
So since this seems more like a OS issue than a Python one, I decided to post here. Suggestions? And let me know if the rebuild is still necessary. Thanks.